Smalltalk/X Webserver

Documentation of class 'LargeInteger':

Class: LargeInteger

Inheritance
Description
Class protocol
Instance protocol

Inheritance:

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

Package:: stx:libbasic

Category:: Magnitude-Numbers

Version:: rev: 1.323 date: 2023/09/25 12:20:24; user: stefan; file: LargeInteger.st directory: libbasic; module: stx stc-classLibrary: libbasic

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 could be rewritten as primitives), although the
common operations have been pretty much 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).

TODO:
    currently, the digitbytes-array may contain any number of (odd) bytes.
    Code should be changed to always allocate multiples of the machine's natural
    word length (i.e. 32 or 64 bits).
    Or even 128bits, if the CPU supports some kind of long-integer vector instructions.
    Currently, stupid code is needed in the loops to first skip over and handle odd-aligned data.

    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.

Emergency break:
    some algorithms may generate huge largeIntegers (eg. series expansions of LargeFloats).
    I ran into code which generated large integers with 100Mb in size, due to bad explosions
    of the number of bits in fractions (precision doubled with every loop iteraltion).

    To enable an emergency break which traps generation of very large integers,
    set the class variable 'SizeLimit' to some integer.
    Then an exception will be raised, whenever a largeInteger is created with more
    than this number of bytes. By default, there is NO such limit.
    A good limit is (say) 10000.
        SizeLimit := nil
        SizeLimit := 10000

copyrightCOPYRIGHT (c) 1994 by Claus Gittinger
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

coercing & converting

coerce: aNumber: convert the argument aNumber into an instance of the receiver (class) and return it.
generality: return the generality value - see ArithmeticValue>>retry:coercing:

instance creation

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.
This can be used to create an unnormalized LargeInteger
(i.e. with a value in the SmallInteger range)

Usage example(s):

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

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.
This can be used to create an unnormalized LargeInteger
(i.e. with a value in the SmallInteger range)

Usage example(s):

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

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.
This can be used to create an unnormalized LargeInteger
(i.e. with a value in the SmallInteger range)

Usage example(s):

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

new

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

new: numberOfDigits

catch creation message

random
( an extension from the stx:libbasic2 package )

LargeInteger random

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

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

Instance protocol:

arithmetic

* aNumber

return the product of the receiver and the argument.

+ aNumber

return the sum of the receiver and the argument, aNumber

Usage example(s):

^ self retry:#+ coercing:aNumber

Usage example(s):

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

- aNumber

return the difference of the receiver and the argument, aNumber

Usage example(s):

^ self retry:#- coercing: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

/ aNumber

return the quotient of the receiver and the argument, aNumber

// 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):

^ self retry:#// coercing:aNumber

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

\\ 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):

^ self retry:#\\ coercing:aNumber

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

abs

return my absolute value. redefined for speed.

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)

negated

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

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

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

squared

return receiver * receiver.

bit operators

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|
     #(
         (1008 1000)
         (1007 1000)
         (1006 1000)
         (1004 1000)
         (1003 1000)
         (1001 1000)
         (1000 1000)
     ) do:[:pair |
         |sz1 sz2|
         sz1 := pair at:1.
         sz2 := pair at:2.
         l1 := LargeInteger digitBytes:(ByteArray new:sz1 withAll:16rFF).
         l2 := LargeInteger digitBytes:(ByteArray new:sz2 withAll:16rAA).
         [
            1000000 timesRepeat:[ rslt := l1 bitAnd:l2 ]
         ] benchmark:'large bitAnd'.
         self assert:(rslt = (LargeInteger digitBytes:(ByteArray new:sz2 withAll:16rAA)))
     ]

Usage example(s):

     |a b|
     a := 1<<300.
     b := 1<<301.
     Time millisecondsToRun:[
        1000000 timesRepeat:[
            a bitAnd:b
        ]
     ]     

     mmx no unroll 180 180 182
     mmx with unroll 193 192

Usage example(s):

     |a b|
     a := 1<<3000.
     b := 1<<3001.
     Time millisecondsToRun:[
        1000000 timesRepeat:[
            a bitAnd:b
        ]
     ]     
     mmx no unroll 452 436
     no mmx no unroll 467 465 467
     no mmx no unroll4 452 453

bitOr: anInteger

return the bitwise-or of the receiver and the argument, anInteger

Usage example(s):

     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r8844) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r11111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r1111111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r111111111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r11111111111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r1111111111111111) hexPrintString
     (16rFFEEDDCCBBAA998877665544332211 bitOr:16r111111111111111111) hexPrintString
     (16rFFEEDDCCBBAA9988776655443322110000000000000000 bitOr:16r1111111111111111110000000000000000) hexPrintString

     |l1 l2 rslt|
     l1 := LargeInteger digitBytes:(ByteArray new:1008 withAll:16rAA).
     l2 := LargeInteger digitBytes:(ByteArray new:1000 withAll:16r55).
     Transcript showCR:(
        Time microsecondsToRun:[
            1000000 timesRepeat:[
                rslt := l1 bitOr:l2.
            ]
        ]).
     self assert:(rslt = (LargeInteger
                            digitBytes:(ByteArray new:1000 withAll:16rFF)
                                       ,(ByteArray new:8 withAll:16rAA)))

     mmx unroll4: 333347 329458 323014 316409 330005 328476
     no mmx, unroll4: 376356 377591 359689 368923 377044 370235
     no mmx, no unroll4: 349378 334986 325504 325758 328631 325177
     no mmx, no unroll: 340230 352629 343654 340623 336606

bitTest: aMaskInteger

return true, if any bit from aMask is set in the receiver.
I.e. true, if the bitwise-AND of the receiver and the argument, anInteger
is non-0, false otherwise.

Usage example(s):

     (16rFFEEDDCCBBAA998877665544332211 bitTest:16rFF)          => true
     (16rFFEEDDCCBBTestAA99887766554433221100 bitTest:16rFF)        => false
     (16rFFEEDDCCBBAA99887766554433221100 bitTest:16rFFFF)      => true

     (16rFFEEDDCCBBAA998877665544332211 bitTest:16rFFFF)        => true
     (16rFFEEDDCCBBAA99887766554433221100 bitTest:16rFFFF)      => true
     (16rFFEEDDCCBBAA9988776655443322110000 bitTest:16rFFFF)    => false
     (16rFFEEDDCCBBAA9988776655443322110000 bitTest:16rFFFFFF)  => true

     (16rFFEEDDCCBBAA9988776655443322110000000000000000 bitTest:16rFFFFFFFFFFFFFFFFFF0000000000000000) => true
     (16rFFEEDDCCBBAA9988776655443322110000000000000000 bitAnd:16rFFFFFFFFFFFFFFFFFF0000000000000000)  => 52244597105217779296040586641974902128640

     (16rFFEEDDCCBBAA9988776655443322110000000000000000 bitTest:16rFFFFFFFFFFFFFFFF) => false

     |a b|
     a := 1<<300.
     b := 1<<301.
     Time millisecondsToRun:[
        1000000 timesRepeat:[
            a bitTest:b
        ]
     ]  
     no unroll 146 153 155 
     with unroll 112 112 111 110

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):

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

     |bigNum1 bigNum2|

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

bitXored: anInteger

Destructive:
place the bitwise-or of the receiver and the argument, anInteger
into the receiver.
Here, a specially tuned version for largeInteger arguments
(to speed up some cryptographic code).
NOTE: This operation changes the receiver and doesn't compress the result!

Usage example(s):

     |bigNum1 bigNum2|

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

Usage example(s):

     |bigNum1 bigNum2|

     bigNum1 := 2 raisedToInteger:512.
     bigNum2 := 2 raisedToInteger:512.
     bigNum1 bitXored:bigNum2.

highBitOfMagnitude

return the high bit index of my magnitude bits
(i.e. of my absolute value)

Usage example(s):

     (1 bitShift:10) highBitOfMagnitude         11
     (1 bitShift:31) highBitOfMagnitude         32
     (1 bitShift:31) negated highBitOfMagnitude 32
     (1 bitShift:100) highBitOfMagnitude         101
     (1 bitShift:100) negated highBitOfMagnitude 101

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.

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

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
     TestCase assert:( (1<<100) bitAt:100 ) == 0
     TestCase assert:( (1<<100) bitAt:101 ) == 1

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
     TestCase assert:(( 16r80000000 setBit:100 ) bitAt:100) == 1
     TestCase assert:(( 16r80000000 setBit:100 ) bitAt:101) == 0
     TestCase assert:(( 16r80000000 setBit:100 ) bitAt:99) == 0

bit operators-32bit

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

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.

bitShift32: shiftCount

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

Usage example(s):

     128 bitShift:24
     128 bitShift32:24

     1 bitShift:31
     1 bitShift32:31

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

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

byteSwapped32

byte swap a 32bit value; lsb -> msb;
i.e. a.b.c.d -> d.c.b.a
Any higher bits are ignored.
Useful for communication protocols

Usage example(s):

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

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
Any higher bits are ignored.
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
     (LargeInteger value:16rFFEEDDCCBBAA9988) byteSwapped64 hexPrintString
     16r88776655 byteSwapped hexPrintString
     16r11223344 byteSwapped hexPrintString
     [ 1000000 timesRepeat:[16r11223344 byteSwapped64]] benchmark:'bswapped'
     [ 1000000 timesRepeat:[16r7766554433221100 byteSwapped64]] benchmark:'bswapped small'
     [ 1000000 timesRepeat:[16rFFEEDDCCBBAA9988 byteSwapped64]] benchmark:'bswapped large'

digitAt: index

return 8 bits of the absolute value, starting at byte index.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

Usage example(s):

     50 factorial digitBytes at:10
     50 factorial digitAt:10

digitAt: index put: aByte

set the 8 bits, index is a byte index.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

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 of a signed integer is returned.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

Usage example(s):

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

digitBytes

return a byteArray filled with the receiver's bits
(8 bits of the absolute value per element).
Least significant byte is first!.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

digitBytesMSB

return a byteArray filled with the receiver's bits
(8 bits of the absolute value per element),
most significant byte first.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

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.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

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!.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).

Usage example(s):

	16r12345678901234567890 digitBytesSigned
	16r-12345678901234567890 digitBytesSigned

digitLength

return the number of bytes needed for the unsigned binary representation of the receiver.
The name 'digit' is a bit misleading: 'digit' here means byte (not decimal digit).
For negative receivers, the result is not defined by the language standard.
ST/X returns the digitLength of its absolute value.
Therefore, do not use this to find out how many bytes are needed
for a negative integer; use #signedDigitLength.

Usage example(s):

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

Usage example(s):

     (SmallInteger maxVal + 1) digitLength          8
     ((SmallInteger maxVal + 1) * 128) digitLength  9
     ((SmallInteger maxVal + 1) * 256) digitLength  9
     ((SmallInteger maxVal + 1) * 512) digitLength  9
     ((SmallInteger maxVal + 1) * 1024) digitLength 10
     ((SmallInteger maxVal + 1) << 1) digitLength   8
     ((SmallInteger maxVal + 1) << 7) digitLength   9
     ((SmallInteger maxVal + 1) << 8) digitLength   9
     ((SmallInteger maxVal + 1) << 9) digitLength   9
     ((SmallInteger maxVal + 1) << 10) digitLength  10
     ((SmallInteger maxVal + 1) << 17) digitLength  10
     ((SmallInteger maxVal + 1) << 18) digitLength  11
     ((SmallInteger maxVal + 1) << 25) digitLength  11
     ((SmallInteger maxVal + 1) << 26) digitLength  12
     ((SmallInteger maxVal + 1) << 33) digitLength  12
     ((SmallInteger maxVal + 1) << 34) digitLength  13

digits

obsolete, use #digitBytes

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

coercing & converting

asLargeInteger

return a LargeInteger with same value as myself - that's me

asSigned32

return a 32-bit signed 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

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 ?
Notice: normally, largeInts in the smallInt range are not created;
however, this may be called on a result (eg. after subtraction) to return
a smallInt result at the end.

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

coerce: aNumber

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

compressed

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

generality

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

nilAllInstvars

100 factorial nilAllInstvars

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

< aNumber

return true, if the argument, aNumber is greater than the receiver

Usage example(s):

aNumber is <= 0

Usage example(s):

aNumber is <= 0

= aNumber

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

> aNumber

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

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

hashMultiply

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

double dispatching

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

equalFromInteger: anInteger

sent when an integer does not know how to compare to the receiver, a largeInt

lessFromInteger: anInteger

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

productFromInteger: anInteger

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

Usage example(s):

     0xFFFFFFFFFFFFFFFF productFromInteger:2
     0xFFFFFFFFFFFFFFFF productFromInteger:-2
     -0xFFFFFFFFFFFFFFFF productFromInteger:2
     -0xFFFFFFFFFFFFFFFF productFromInteger:-2

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

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

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

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

absEq: aLargeInteger

return true, if abs(self) = abs(theArgument)

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))

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

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))

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.

absLess: aLargeInteger

return true, if abs(self) < abs(theArgument).
This handles unnormalized largeIntegers.

Usage example(s):

     |a b|

     a := 16rFEFFFFFF.
     b := 16rFFFFFFFF.
     Time millisecondsToRun:[
       10000000 timesRepeat:[ a absLess_old:b ]
     ]    1185 1233 1185

     |a b|

     a := 16rFEFFFFFF.
     b := 16rFFFFFFFF.
     Time millisecondsToRun:[
       10000000 timesRepeat:[ a absLess_n:b ]
     ] 686 655 702 702

     16rEFFFFFFF  absLess_n: 16rFFFFFFFF
     16rEFFFFFFF  absLess: 16rFFFFFFFF

absLessEq: aLargeInteger

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

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.

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

absMul: aLargeInteger

return a LargeInteger representing abs(self) * abs(theArgument)

absMulKarazuba: anInteger

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 for 32-bit
and 8000bits/digitLength of 1000 for 64-bit.
(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) + 1111111.
	 Transcript show:exp; show:' nbytes: '; showCR:nr digitLength;
	    show:'  normal: '; showCR:(TimeDuration toRun:[ UseKarazuba := false. r1 := nr * nr ]);
	    show:'  karazuba: '; showCR:(TimeDuration toRun:[ UseKarazuba := true. r2 := nr absMulKarazuba: nr]).
	 self assert:(r1 = r2).
     ]

     self assert:((3 raisedTo:10000) absMulKarazuba:11111) = (11111 * (3 raisedTo:10000))

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.

destructiveAbs

kludge: make the receiver its absolute value in place.
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

destructiveNegated

kludge: negate the receiver in place.
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

div2

private helper for division:
destructively divide the receiver by 2.
may leave the receiver unnormalized (i.e. with a leftover 0 high-byte).
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

Usage example(s):

     100000 asLargeInteger div2
     1000000000000000000000000000 div2
     10000000000000000000000000000000000000000000 div2

mul2

private helper for division:
destructively multiply the receiver by 2.
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

Usage example(s):

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

mul256

private helper for division:
destructively multiply the receiver by 256.
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

numberOfDigits: nDigits

allocate space for nDigits bytes of magnitude

numberOfDigits: nDigits sign: newSign

allocate space for nDigits bytes of magnitude

setDigits: digits

set the digits from the lsb-ordered digit-bytes

setDigits: aByteArray sign: newSign

set the digits from the lsb-ordered digit-bytes

setSign: aNumber

destructively change the sign of the receiver.
Return the compressed integer (smallinteger if possible).
You may only ever use this on receivers which are known to be strictly
private to your algorithm
(i.e. the receiver must be a temporary scratch-number)

Usage example(s):

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

queries

isZero

return true, if the receiver is zero

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):

     0 nextPowerOf2 -> 0
     1 nextPowerOf2 -> 1
     2 nextPowerOf2 -> 2
     125 nextPowerOf2 -> 128
     127 nextPowerOf2 -> 128
     128 nextPowerOf2 -> 128
     129 nextPowerOf2 -> 256
     0x80 nextPowerOf2 -> 256
     0xFF nextPowerOf2 -> 256
     0xFF00 nextPowerOf2 -> 65536
     0xFF0000 nextPowerOf2 -> 16r1000000
     0xFF000000 nextPowerOf2 -> 16r100000000
     0xFF00000000 nextPowerOf2 -> 16r10000000000
     0xFF0000000000 nextPowerOf2 -> 16r1000000000000
     0xFF000000000000 nextPowerOf2 -> 16r100000000000000
     0xFF00000000000000 nextPowerOf2 -> 16r10000000000000000

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

testing

even

return true if the receiver is even

Usage example(s):

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

negative

return true, if the receiver is less than zero

odd

return true if the receiver is odd

positive

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

sign

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

strictlyPositive

return true, if the receiver is greater than zero

ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Mon, 18 Nov 2024 04:36:28 GMT