eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'LargeInteger':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: LargeInteger


Inheritance:

   Object
   |
   +--Magnitude
      |
      +--ArithmeticValue
         |
         +--Number
            |
            +--Integer
               |
               +--LargeInteger

Package:
stx:libbasic
Category:
Magnitude-Numbers
Version:
rev: 1.271 date: 2019/03/22 11:55:08
user: cg
file: LargeInteger.st directory: libbasic
module: stx stc-classLibrary: libbasic
Author:
Claus Gittinger

Description:


This class provides arbitrary precision integers.
These are represented as:
  sign (-1/0/+1) and, if sign ~~ 0
  the absolute value in a ByteArray of digits with 8 bits per element;
  least significant 8 bits at index 1...

The implementation is not completely tuned for high performance
(more key-methods should be rewritten as primitives), although the
common operations have been pretty tuned for some architectures.

LargeIntegers are usually not created explicitely, but result from
SmallInteger arithmetic (overflowing the SmallInteger range).
Also, results of LargeInteger operations are converted to back to
SmallIntegers, when possible (see #compressed).

In contrast to ST-80, there is only one class for LargeIntegers,
which keeps the sign as an instance variable
(ST-80 has LargePositiveInteger and LargeNegativeInteger).
Another possible change is to use 2's complement instead of sign-magnitude
representation, and to use the underlying CPU's native byte order (instead of LSB).
This would allow us to use modern CPU vector/longword operations, at least for 64 and
128 bit numbers (which make up almost all instances in practice).
As all of these are transparent to the outside world, any of it may or may not
change in the future.


Related information:

    Number
    Float
    Fraction
    FixedPoint
    SmallInteger

Class protocol:

coercing & converting
o  coerce: aNumber
convert the argument aNumber into an instance of the receiver's class and return it.

instance creation
o  digitBytes: aByteArrayOfDigits
create and return a new LargeInteger with digits (lsb-first)
from the argument, aByteArray.
The byteArray argument provides the unsigned magnitude in lsb-first order.

usage example(s):

     LargeInteger digitBytes:#[16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF]
     (LargeInteger digitBytes:#[16r12 16r34 16r56 16r78 16r90]) hexPrintString

o  digitBytes: aByteArrayOfDigits MSB: msb
create and return a new LargeInteger with digits (which may be in either msb/lsb order)
from the argument, aByteArray.
The byteArray argument provides the unsigned magnitude in the specified byte order.

usage example(s):

     (LargeInteger digitBytes:#[16r10 16r20 16r30 16r40] MSB:false) hexPrintString
     (LargeInteger digitBytes:#[16r10 16r20 16r30 16r40] MSB:true) hexPrintString

o  digitBytes: aByteArrayOfDigits sign: sign
create and return a new sign-magnitude LargeInteger with digits (lsb-first)
from the argument, aByteArray.
The byteArray argument provides the unsigned magnitude in lsb-first order.

usage example(s):

     LargeInteger digitBytes:#[16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF]
     (LargeInteger digitBytes:#[16r12 16r34 16r56 16r78 16r90]) hexPrintString

o  new
catch creation message.
LargeIntegers are only created by system code, which
uses basicNew and cares for correct initialization.

o  new: numberOfDigits
catch creation message

o  value: aSmallInteger
create and return a new LargeInteger with value taken from
the argument, aSmallInteger.
Notice:
this should be only used internally, since such small
largeIntegers do not normally occur in the system.
(They are used by myself)
May change/be removed without notice.

usage example(s):

LargeInteger value:3689

queries
o  isBuiltInClass
return true if this class is known by the run-time-system.
Here, true is returned.


Instance protocol:

arithmetic
o  * aNumber
return the product of the receiver and the argument.

o  + aNumber
return the sum of the receiver and the argument, aNumber

usage example(s):

     SmallInteger maxVal
     SmallInteger maxVal + 1
     SmallInteger maxVal + 2
     SmallInteger minVal
     SmallInteger minVal - 1

o  - aNumber
return the difference of the receiver and the argument, aNumber

usage example(s):

     12345678901234567890 - 0
     12345678901234567890 - 1
     12345678901234567890 - -1
     -12345678901234567890 - 1
     -12345678901234567890 - -1

     12345678901234567890 - 12345678901234567880
     12345678901234567890 - 12345000000000000000
     12345678901234567890 - -87654321098765432110
     -12345678901234567890 - 87654321098765432110
     -12345678901234567890 - -12345678901234567880
     -12345678901234567890 - -12345678901234567980

o  / aNumber
return the quotient of the receiver and the argument, aNumber

o  // aNumber
return the integer part of the quotient of the receiver's value
and the argument's value.
The result is truncated toward negative infinity
and will be negative, if the operands signs differ.
The following is always true:
(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver

Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
Especially surprising (because of truncation toward negative infinity):
-1 // 10 -> -1 (because -(1/10) is truncated towards next smaller integer, which is -1.
-10 // 3 -> -4 (because -(10/3) is truncated towards next smaller integer, which is -4.

See #quo: which truncates toward zero and returns -2 in the above case
and #rem: which is the corresponding remainder.

usage example(s):

     (9000000000 // 4000000000)   =   (900 // 400)   ifFalse:[self halt].
     (-9000000000 // 4000000000)  =   (-900 // 400)  ifFalse:[self halt].
     (9000000000 // -4000000000)  =   (900 // -400)  ifFalse:[self halt].
     (-9000000000 // -4000000000) =   (-900 // -400) ifFalse:[self halt].

     16rfffffffff // 16r01ffffff  =   2048 ifFalse:[self halt].
     16rfffffffff // 16r00ffffff  =   4096 ifFalse:[self halt].
     16rfffffffff // 16r001fffff  =  32768 ifFalse:[self halt].

     900 quo: 400
     -900 quo: 400
     900 quo: -400
     -900 quo: -400

     9000000000 quo: 4000000000
     -9000000000 quo: 4000000000
     9000000000 quo: -4000000000


     0 // 40000000000000000

o  \\ aNumber
Answer the integer remainder m defined by division with truncation toward
negative infinity.
m < |aNumber| AND there is an integer k with (k * aNumber + m) = self

The returned remainder has the same sign as aNumber.
The following is always true:
(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver

Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
Especially surprising:
-1 \\ 10 -> 9 (because -(1/10) is truncated towards next smaller integer, which is -1,
and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
-10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
and -4 * 4 gives -12, so we need to add 2 to get the original -10.

See #rem: which is the corresponding remainder for division via #quo:.

Redefined here for speed.

usage example(s):

     (9000000000 \\ 4000000000)   = (900 \\ 400 * 10000000)  ifFalse:[self halt].
     (-9000000000 \\ 4000000000)  = (-900 \\ 400 * 10000000) ifFalse:[self halt].
     (9000000000 \\ -4000000000)  = (900 \\ -400 * 10000000) ifFalse:[self halt].
     (-9000000000 \\ -4000000000) = (-900 \\ -400 * 10000000)ifFalse:[self halt].
     (16000000000 \\ 4000000000)  = (1600 \\ 400 * 10000000) ifFalse:[self halt].
     (-16000000000 \\ 4000000000)  = (-1600 \\ 400 * 10000000) ifFalse:[self halt].
     (16000000000 \\ -4000000000)  = (1600 \\ -400 * 10000000) ifFalse:[self halt].
     (-16000000000 \\ -4000000000)  = (-1600 \\ -400 * 10000000) ifFalse:[self halt].

     9000000000 \\ 7
     -9000000000 \\ 7
     9000000000 \\ -7
     -9000000000 \\ -7

     900 rem: 400
     -900 rem: 400
     900 rem: -400
     -900 rem: -400

     9000000000 rem: 4000000000
     -9000000000 rem: 4000000000
     9000000000 rem: -4000000000
     -9000000000 rem: -4000000000

o  abs
return my absolute value. redefined for speed.

o  divMod: aNumber
return an array filled with
(self // aNumber) and (self \\ aNumber).
The returned remainder has the same sign as aNumber.
The following is always true:
(receiver // something) * something + (receiver \\ something) = receiver

Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
Especially surprising:
-1 \\ 10 -> 9 (because -(1/10) is truncated towards next smaller integer, which is -1,
and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
-10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
and -4 * 4 gives -12, so we need to add 2 to get the original -10.

This is redefined here for more performance
(as the remainder is generated as a side effect of division)

usage example(s):

     9000000000 // 4000000000   => 2
     9000000000 \\ 4000000000   => 1000000000

     9000000000 divMod: 4000000000   => #(2 1000000000)
     -9000000000 divMod: 4000000000   => #(-3 3000000000)
     9000000000 divMod: -4000000000   => #(-3 -3000000000)
     -9000000000 divMod: -4000000000   => #(2 -1000000000)

     9000000000000000000 absDivMod: 400000000000000   => #(22500 0)
     -9000000000000000000 absDivMod: 400000000000000   => #(22500 0)
     9000000000000000000 absDivMod: -400000000000000   => #(22500 0)
     -9000000000000000000 absDivMod: -400000000000000   => #(22500 0)

     9000000000000000000 absDivMod: 4000000000000000   => #(2250 0)
     -9000000000000000000 absDivMod: 4000000000000000   => #(2250 0)
     9000000000000000000 absDivMod: -4000000000000000   => #(2250 0)
     -9000000000000000000 absDivMod: -4000000000000000   => #(2250 0)

     9000000000000000000 absDivMod: 4000000000000000000   => #(2 1000000000000000000)
     -9000000000000000000 absDivMod: 4000000000000000000   => #(2 1000000000000000000)
     9000000000000000000 absDivMod: -4000000000000000000   => #(2 1000000000000000000)
     -9000000000000000000 absDivMod: -4000000000000000000   => #(2 1000000000000000000)

o  negated
return an integer with value negated from the receiver's value.

o  quo: aNumber
return the quotient of the receiver and the argument, aNumber.
The result is truncated toward zero (which is different from //, which
truncates toward negative infinity).
The result's sign is negative if the receiver has a sign different from the arg's sign.
The following is always true:
(receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver
For positive results, this is the same as #//,
for negative results, the remainder is ignored.
I.e.: '9 // 4 = 2' and '-9 // 4 = -3'
in contrast: '9 quo: 4 = 2' and '-9 quo: 4 = -2'

usage example(s):

     900 // 400
     -900 // 400
     900 // -400
     -900 // -400

     9000000000 // 4000000000
     -9000000000 // 4000000000
     9000000000 // -4000000000
     -9000000000 // -4000000000

     900 quo: 400
     -900 quo: 400
     900 quo: -400
     -900 quo: -400

     9000000000 quo: 4000000000
     -9000000000 quo: 4000000000
     9000000000 quo: -4000000000
     -9000000000 quo: -4000000000

o  rem: aNumber
return the remainder of division of the receiver by the argument, aNumber.
The returned remainder has the same sign as the receiver.
The following is always true:
(receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver

usage example(s):

     900 \\ 400
     -900 \\ 400
     900 \\ -400
     -900 \\ -400

     9000000000 \\ 4000000000
     -9000000000 \\ 4000000000
     9000000000 \\ -4000000000
     -9000000000 \\ -4000000000

     900 rem: 400
     -900 rem: 400
     900 rem: -400
     -900 rem: -400

     9000000000 rem: 4000000000
     -9000000000 rem: 4000000000
     9000000000 rem: -4000000000
     -9000000000 rem: -4000000000

bit operators
o  bitAnd: anInteger
return the bitwise-and of the receiver and the argument, anInteger

usage example(s):

     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFFFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitAnd:16rFFFFFFFFFFFFFFFFFF) hexPrintString
     (16rFFEEDDCCBBAA9988776655443322110000000000000000 bitAnd:16rFFFFFFFFFFFFFFFFFF0000000000000000) hexPrintString

     |l1 l2 rslt|
     l1 := LargeInteger digitBytes:(ByteArray new:1008 withAll:16rFF).
     l2 := LargeInteger digitBytes:(ByteArray new:1000 withAll:16rAA).
     Fast := false.
     Transcript showCR:(
        Time microsecondsToRun:[
            10000 timesRepeat:[
                rslt := l1 bitAnd:l2.
            ]
        ]).     
     Transcript showCR:Fast.
     self assert:(rslt = (LargeInteger digitBytes:(ByteArray new:1000 withAll:16rAA)))

o  bitXor: anInteger
return the bitwise-or of the receiver and the argument, anInteger.
Here, a specially tuned version for largeInteger arguments
(to speed up some cryptographic code)

usage example(s):

     (16r112233445566778899 bitXor:16rFF                ) printStringRadix:16 '112233445566778866'
     (16r112233445566778899 bitXor:16rFFFFFFFFFFFFFFFF00) printStringRadix:16 'EEDDCCBBAA99887799'
     (16r112233445566778899 bitXor:16rFF0000000000000000) printStringRadix:16 'EE2233445566778899'
     (16r112233445566778899 bitXor:16r112233445566778800) printStringRadix:16 '99'

     |bigNum1 bigNum2|

     bigNum1 := 2 raisedToInteger:512.
     bigNum2 := 2 raisedToInteger:510.
     Time millisecondsToRun:[
	1000000 timesRepeat:[
	   bigNum1 bitXor:bigNum2.
	]
     ]

o  lowBit
return the bitIndex of the lowest bit set. The returned bitIndex
starts at 1 for the least significant bit.
Returns 0 if no bit is set.
For negative numbers, the low bit of my absolute value is returned.
Redefined here for more performance of the gcd: algorithm, which
is used when big fractions are reduced (should we write a primitive for this ?).

usage example(s):

     (1 bitShift:0) lowBit
     (1 bitShift:10) lowBit
     (1 bitShift:20) lowBit
     (1 bitShift:30) lowBit
     (1 bitShift:30) highBit
     (1 bitShift:31) lowBit
     (1 bitShift:31) highBit
     (1 bitShift:32) lowBit
     (1 bitShift:32) highBit
     (1 bitShift:33) lowBit
     (1 bitShift:33) highBit
     (1 bitShift:64) lowBit
     (1 bitShift:64) highBit
     (1 bitShift:1000) lowBit
     (1 bitShift:1000) highBit
     ((1 bitShift:64)-1) lowBit
     ((1 bitShift:64)-1) highBit

     1 to:1000 do:[:idx |
	self assert:(( 1 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 1 bitShift:idx) lowBit = ( 1 bitShift:idx) highBit).
	self assert:(( 3 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 7 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 15 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 31 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 63 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 127 bitShift:idx) lowBit = (idx+1)).
	self assert:(( 255 bitShift:idx) lowBit = (idx+1)).
     ]

     |num|

     num := (1 bitShift:1000).
     Time millisecondsToRun:[
	1000000 timesRepeat:[
	    num lowBit
	]
     ]

bit operators - indexed
o  bitAt: anIntegerIndex
return the value of the index's bit (index starts at 1) as 0 or 1.
Notice: the result of bitAt: on negative receivers is not
defined in the language standard (since the implementation
is free to choose any internal representation for integers)

usage example(s):

     TestCase should:[ 16rFFFFFFFFFF01 bitAt:0 ] raise:Error
     TestCase assert:( 16rFFFFFFFFFF01 bitAt:49 ) == 0
     TestCase assert:( 16rFFFFFFFFFF01 bitAt:1  ) == 1
     TestCase assert:( 16rFFFFFFFFFF01 bitAt:2  ) == 0
     TestCase assert:( 16rFFFFFFFFFF02 bitAt:2  ) == 1
     TestCase assert:( 16rFFFFFFFF01FF bitAt:8  ) == 1
     TestCase assert:( 16rFFFFFFFF01FF bitAt:9  ) == 1
     TestCase assert:( 16rFFFFFFFF01FF bitAt:10 ) == 0

o  setBit: index
return a new integer, where the specified bit is on.
Bits are counted from 1 starting with the least significant.
The method's name may be misleading: the receiver is not changed,
but a new number is returned. Should be named #withBitSet:

usage example(s):

     TestCase assert:( 16r80000000 setBit:3  ) = 16r80000004
     TestCase assert:( 16r80000000 setBit:33 ) = 16r180000000

bit operators-32bit
o  bitInvert32
return the value of the receiver with all bits inverted in 32bit signed int space
(changes the sign)

usage example(s):

     16r80000000 bitInvert32 hexPrintString
     16r7FFFFFFF bitInvert32 hexPrintString
     16rFFFFFFFF bitInvert32 hexPrintString
     0 bitInvert32 hexPrintString

o  bitRotate32: shiftCount
return the value of the receiver rotated by shiftCount bits,
but only within 32 bits, rotating left for positive, right for negative counts.
Rotates through the sign bit.
Useful for crypt algorithms, or to emulate C/Java semantics.

o  bitShift32: shiftCount
return the value of the receiver shifted by shiftCount bits,
but only within 32 bits, shifting into/out-of the sign bit.
May be useful for communication interfaces, to create ST-numbers
from a signed 32bit int value given as individual bytes,
or to emulate C/Java semantics.
The shift is unsigned

usage example(s):

     128 bitShift:24
     128 bitShift32:24

     1 bitShift:31
     1 bitShift32:31

o  bitXor32: aNumber
return the xor of the receiver and the argument.
The argument must be a SmallInteger or a 4-byte LargeInteger.
If the result overflows the 32 bit range, the value modulo 16rFFFFFFFF is returned.
This is of course not always correct, but allows for C/Java behavior to be emulated.

usage example(s):

     16r7FFFFFFF bitXor: 16r80000000          4294967295
     16r7FFFFFFF bitXor32: 16r80000000

byte access
o  byteSwapped
lsb -> msb;
i.e. a.b ... y.z -> z.y. ... b.a

usage example(s):

     (LargeInteger value:16r11223344) byteSwapped hexPrintString
     (LargeInteger value:16r44332211) byteSwapped hexPrintString
     16r88776655 byteSwapped hexPrintString
     16r11223344 byteSwapped hexPrintString

o  byteSwapped32
byte swap a 32bit value; lsb -> msb;
i.e. a.b.c.d -> d.c.b.a
Useful for communication protocols

usage example(s):

     (LargeInteger value:16r11223344) byteSwapped32 hexPrintString
     (LargeInteger value:16r44332211) byteSwapped32 hexPrintString
     16r88776655 byteSwapped32 hexPrintString
     16r11223344 byteSwapped32 hexPrintString

o  byteSwapped64
byte swap a 64bit value; lsb -> msb;
i.e. a.b.c.d.e.f.g.h -> h.g.f.e.d.c.b.a
Useful for communication protocols

usage example(s):

     (LargeInteger value:16r11223344) byteSwapped64 hexPrintString
     (LargeInteger value:16r44332211) byteSwapped64 hexPrintString
     (LargeInteger value:16r1122334455667788) byteSwapped64 hexPrintString
     (LargeInteger value:16r8877665544332211) byteSwapped64 hexPrintString
     16r88776655 byteSwapped hexPrintString
     16r11223344 byteSwapped hexPrintString

o  digitAt: index
return 8 bits of value, starting at byte index

o  digitAt: index put: aByte
set the 8 bits, index is a byte index

o  digitByteAt: index
return 8 bits of my signed value, starting at byte index.
For positive receivers, this is the same as #digitAt:;
for negative ones, the actual bit representation is returned.

usage example(s):

     16r11111111111111111111 negated digitByteAt:1
     0 asLargeInteger digitByteAt:1
     -1 asLargeInteger digitByteAt:1
     -1 digitByteAt:1

o  digitBytes
return a byteArray filled with the receiver's bits
(8 bits of the absolute value per element).
Least significant byte is first!

o  digitBytesMSB
return a byteArray filled with the receiver's bits
(8 bits of the absolute value per element),
most significant byte first

o  digitBytesMSB: msbFlag
return a byteArray filled with the receiver's bits
(8 bits of the absolute value per element),
if msbflag = true, most significant byte is first,
otherwise least significant byte is first

o  digitBytesSigned
return a byteArray filled with the receiver's bits
(8 bits of the value (which may be negative) per element).
Least significant byte is first!

usage example(s):

        16r12345678901234567890 digitBytesSigned
        16r-12345678901234567890 digitBytesSigned

o  digitLength
return the number of bytes needed for the unsigned binary representation of the receiver.
For negative receivers, the result is not defined by the language standard.
ST/X returns the digitLength of its absolute value.

usage example(s):

     check if there is a 0-byte ...
     this allows to ask unnormalized LargeIntegers
     for their digitLength

o  digits
obsolete, use #digitBytes

** This is an obsolete interface - do not use it (it may vanish in future versions) **

coercing & converting
o  asLargeInteger
return a LargeInteger with same value as myself - that's me

o  asSigned32
return a 32-bit integer with my bit-pattern. Receiver must be unsigned (i.e. positive).
May be required for bit operations on the sign-bit and/or to
convert C/Java numbers.

usage example(s):

     16r80000000 asSigned32
     16r40000000 asSigned32

o  asSmallInteger
return a SmallInteger with same value as myself -
the result is invalid if the receiver's value cannot
be represented as a SmallInteger.
Q: should we raise an exception if this happens ?

o  asUnsigned32
return a 32-bit integer with my bit-pattern. Receiver must be unsigned (i.e. positive).
May be required for bit operations on the sign-bit and/or to
convert C/Java numbers.

usage example(s):

     16r80000000 asUnsigned32
     16r40000000 asUnsigned32

o  coerce: aNumber
convert the argument aNumber into an instance of the receiver's class and return it.

o  compressed
if the receiver can be represented as a SmallInteger, return
a SmallInteger with my value;
otherwise remove leading zero bytes in the digitByte array
and return the receiver

o  generality
return the generality value - see ArithmeticValue>>retry:coercing:

o  nilAllInstvars
100 factorial nilAllInstvars

o  value: aSmallInteger
setup my contents to represent the same value as aSmallInteger.
This method will fail, if the argument is not a smallInteger.
This should only be used internally,
since it will create an unnormalized LargeInt (by purpose) if asked for.

comparing
o  < aNumber
return true, if the argument, aNumber is greater than the receiver

usage example(s):

aNumber is <= 0

usage example(s):

aNumber is <= 0

o  = aNumber
return true, if the argument represents the same numeric value
as the receiver, false otherwise

o  > aNumber
return true, if the argument, aNumber is less than the receiver

o  hash
return an integer useful for hashing on large numbers

usage example(s):

I am really an unnormalized SmallInteger, answer the same hash as for the SmallInteger

usage example(s):

However, we will not change it, but keep it that way, in case the hashvalue already found

usage example(s):

     16r80000000 hash
     16r-80000000 asLargeInteger hash
     16r80000008 hash
     16r8000000000008 hash

     16r8000000000000000 hash
     16r8000000000000008 hash
     16r800000000000000000008 hash
     16r-800000000000000000008 hash

o  hashMultiply
used in some squeak code to generate an alternative hash value for integers

double dispatching
o  differenceFromInteger: anInteger
sent, when anInteger does not know how to subtract the receiver.
Return the result of 'anInteger - self'. The argument must be a SmallInteger.

usage example(s):

     12345678901234567890
     -12345678901234567890
     12345678901234567890 differenceFromInteger:0
     12345678901234567890 differenceFromInteger:1
     12345678901234567890 differenceFromInteger:-1
     -12345678901234567890 differenceFromInteger:1
     -12345678901234567890 differenceFromInteger:-1

o  equalFromInteger: anInteger
sent when an integer does not know how to compare to the receiver, a largeInt

o  lessFromInteger: anInteger
sent when an integer does not know how to compare to the receiver, a largeInt.
Return true if anInteger < self

o  productFromInteger: anInteger
sent, when anInteger does not know how to multiply the receiver.
Return the product of the receiver and the argument, aSmallInteger

o  sumFromInteger: anInteger
sent, when anInteger does not know how to add the receiver.
Return the sum of the receiver and the argument, (which must be a SmallInteger)

usage example(s):

     12345678901234567890
     -12345678901234567890
     12345678901234567890 sumFromInteger:0
     -12345678901234567890 sumFromInteger:0
     12345678901234567890 sumFromInteger:1
     12345678901234567890 sumFromInteger:-1
     -12345678901234567890 sumFromInteger:1
     -12345678901234567890 sumFromInteger:-1

modulo arithmetic
o  plus32: aNumber
return the sum of the receiver and the argument, as SmallInteger.
The argument must be another SmallInteger.
If the result overflows the 32 bit range, the value modulo 16rFFFFFFFF is returned.
This is of course not always correct, but allows for C/Java behavior to be emulated.

usage example(s):

     16r7FFFFFFF + 1       ->  2147483648
     16r7FFFFFFF plus32: 1 ->  -2147483648

private
o  absDestructiveSubtract: aLargeInteger
private helper for division:
destructively subtract aLargeInteger from myself
AND return true, if the result is non-zero, false otherwise.
(i.e. this method has both a return value and a side-effect on the receiver)
Does not care about the signs of the receiver and argument
The receiver must be >= the argument.
The receiver must be a temporary scratch-number

o  absDivMod: anInteger
return an array with two LargeIntegers representing
abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument).
Used as a helper for \\, //, rem: and quo:.
This method needs a rewrite.

usage example(s):

     Time millisecondsToRun:[ 10000 timesRepeat:[  16000000000 absDivMod:4000000000] ]
     Time millisecondsToRun:[ 10000 timesRepeat:[  16000000000 absDivMod:3000000000] ]
     16000000000 absDivMod:4000000000
     16000000000 absDivMod:3000000000
     160000000000000000000000 absDivMod:160000000000000000000000

o  absEq: aLargeInteger
return true, if abs(self) = abs(theArgument)

o  absFastDivMod: aPositiveSmallInteger
return an array with two LargeIntegers representing
abs(self) // aPositiveSmallInteger and
abs(self) \\ aPositiveSmallInteger
or nil, if not computed by optimized code

usage example(s):

     16r123412341234 asLargeInteger absDivMod:(LargeInteger value:10)
     ((16r1234 asLargeInteger absFastDivMod:16rffff) at:2) printStringRadix:16
     ((16r00123456 asLargeInteger absFastDivMod:16rffffff) at:2) printStringRadix:16
     ((666666666666666666 asLargeInteger absFastDivMod:16r3))
     ((1666666666 asLargeInteger absFastDivMod:16r3))

o  absFastMinus: aSmallInteger sign: newSign
return a LargeInteger representing abs(self) - abs(theArgument)
with sign: newSign.
The result is normalized.
This is a helper for addition and subtraction - not for public use.

usage example(s):

     12345678900000000000 absFastMinus:1 sign:1
     12345678900000000000 absFastMinus:1 sign:-1
     12345678900000000000 absFastMinus:1000000 sign:1
     12345678900000000000 absFastMinus:255 sign:1
     (SmallInteger maxVal + 1) absFastMinus:1 sign:1
     (SmallInteger minVal - 1) absFastMinus:1 sign:1

o  absFastMod: aPositiveSmallInteger
return abs(self) \\ aPositiveSmallInteger
or nil, if not computed by optimized code

usage example(s):

     16r123412341234 asLargeInteger absFastDivMod:10 #(2001485300178 0)
     16r123412341234 asLargeInteger absFastMod:10
     
     ((16r1234 asLargeInteger absFastDivMod:16rffff) at:2)
     (16r1234 asLargeInteger absFastMod:16rffff)

     ((16r00123456 asLargeInteger absFastDivMod:16rffffff) at:2)
     (16r00123456 asLargeInteger absFastMod:16rffffff) 

     (666666666666666666 asLargeInteger absFastDivMod:16r3)
     (666666666666666666 asLargeInteger absFastMod:16r3)

     (1666666666 asLargeInteger absFastDivMod:16r3)
     ((1666666666 asLargeInteger absFastMod:16r3))

o  absFastPlus: aSmallInteger sign: newSign
return a LargeInteger representing abs(self) + abs(theArgument).
with sign: newSign.
The result is normalized. The argument must be a smallInteger
with byteSize one less than the integer byteSize.
This is a helper for addition and subtraction - not for public use.

o  absLess: aLargeInteger
return true, if abs(self) < abs(theArgument).
This handles unnormalized largeIntegers.

o  absLessEq: aLargeInteger
return true, if abs(self) <= abs(theArgument).
This handles unnormalized largeIntegers.

o  absMinus: aLargeInteger sign: newSign
return a LargeInteger representing abs(self) - abs(theArgument)
with sign: newSign.
The result is normalized. The argument must be a largeInteger
with a byteSize smaller than the receiver's byteSize.
This is a helper for addition and subtraction - not for public use.

o  absMod: anInteger
return the remainder from the expression:
abs(self) \\ abs(theArgument).
Used as a helper for \\ and rem:

usage example(s):

Time millisecondsToRun:[   100000 timesRepeat:[  16000000000000000000001 absDivMod:4000000000000000000001] ]
Time millisecondsToRun:[   100000 timesRepeat:[  16000000000000000000001 absMod:4000000000000000000001] ]

     16000000000 absMod:4000000000
     16000000000 absMod:3000000000
     16000000000000000000 absMod:16000000000000000000

o  absMul: aLargeInteger
return a LargeInteger representing abs(self) * abs(theArgument)

o  absMulKarazuba: aLargeInteger
return a LargeInteger representing abs(self) * abs(theArgument) using the karazuba algorithm.
a = (2^n * p) + q
b = (2^n * r) + s
a * b = ((2^n * p) + q) * ((2^n * r) + s)
= 2^(n+n)*p*r + 2^n*p*s + 2^n*q*r + q*s
= 2^(n+n)*p*r + (p*r + q*s - (q-p)*(s-r))*2^n + q*s

this is faster for sufficient large n1,n2
because regular multiplication is O(n1*n2) and karazuma multiplies much smaller numbers
(half number of bits) but does more multiplications (on smaller numbers) and req's more
additions and subtractions (on smaller numbers).
The break-even for when to use regular multiplication has been determined heuristically
and is somewhere around 1600 bits (digitLength of 200).
(see test in absMul:)

To disable karazuba, set UseKarazuba to false.

usage example(s):

     #(100 500 1000 2500 5000 10000 25000 50000 100000 250000 500000 1000000) do:[:exp |
	 |nr r1 r2|
	 nr := (3 raisedTo:exp) asInteger.
	 Transcript show:exp; show:' nbytes: '; showCR:nr digitLength;
	    show:'  normal: '; show:(Time microsecondsToRun:[ UseKarazuba := false. r1 := nr * nr ]); showCR:'us';
	    show:'  karazuba: '; show:(Time microsecondsToRun:[ UseKarazuba := true. r2 := nr absMulKarazuba: nr]); showCR:'us'.
	 self assert:(r1 = r2).
     ]

o  absPlus: aLargeInteger sign: newSign
return a LargeInteger representing abs(self) + abs(theArgument)
with sign: newSign.
The result is normalized. The argument must be a smallInteger
with byteSize one less than the integer byteSize.
This is a helper for addition and subtraction - not for public use.

o  div2
private helper for division:
destructively divide the receiver by 2.
may leave the receiver unnormalized (i.e. with a leftover 0 high-byte)

usage example(s):

     100000 asLargeInteger div2
     1000000000000000000000000000 div2
     10000000000000000000000000000000000000000000 div2

o  mul2
private helper for division:
destructively multiply the receiver by 2.

usage example(s):

     100000 asLargeInteger mul2
     16r7FFFFFFFFFFF copy mul2 hexPrintString
     16rFFFFFFFFFFFF copy mul2 hexPrintString
     16r7FFFFFFFFFFFFF copy mul2 hexPrintString
     16rFFFFFFFFFFFFFF copy mul2 hexPrintString
     10000000000000000000000000000 mul2

o  mul256
private helper for division:
destructively multiply the receiver by 256.

o  numberOfDigits: nDigits
allocate space for nDigits bytes of magnitude

o  numberOfDigits: nDigits sign: newSign
allocate space for nDigits bytes of magnitude

o  setDigits: digits
set the digits from the lsb-ordered digit-bytes

o  setDigits: digits sign: newSign
set the digits from the lsb-ordered digit-bytes

o  setSign: aNumber
destructively change the sign of the receiver.
Return the compressed integer (smallinteger if possible)

usage example(s):

     (LargeInteger digitBytes:#[0 0 0 64]) setSign:-1

queries
o  isZero
the integer zero is always represented as a SmallInteger

o  nextPowerOf2
return the power of 2 at or above the receiver.
Notice, that for a powerOf2, the receiver is returned.
Also notice, that (because it is used for padding),
0 is returned for zero.

usage example(s):

     100 factorial nextPowerOf2  isPowerOf:2
     1000 factorial nextPowerOf2  isPowerOf:2
     Time millisecondsToRun:[
	 |v|
	 v := 1000 factorial.
	 1000 timesRepeat:[
	    v nextPowerOf2
	 ]
     ]

testing
o  even
return true if the receiver is even

usage example(s):

     16r100000000000000000001 even
     16r100000000000000000001 odd
     16r100000000000000000000 even
     16r100000000000000000000 odd

o  negative
return true, if the receiver is less than zero

o  odd
return true if the receiver is odd

o  positive
return true, if the receiver is greater or equal to zero (not negative)

o  sign
return the sign of the receiver (-1, 0 or 1)

o  strictlyPositive
return true, if the receiver is greater than zero



ST/X 7.2.0.0; WebServer 1.670 at bd0aa1f87cdd.unknown:8081; Sat, 28 May 2022 20:08:30 GMT