"
 COPYRIGHT (c) 1988-93 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.
"

Number subclass:#Integer
       instanceVariableNames:''
       classVariableNames:''
       poolDictionaries:''
       category:'Magnitude-Numbers'
!

Integer comment:'

COPYRIGHT (c) 1988-93 by Claus Gittinger
              All Rights Reserved

abstract superclass for all integer numbers

%W% %E%
written 88 by claus
'!

!Integer class methodsFor:'constants'!

zero
    ^ 0
!

unity
    ^ 1
! !

!Integer methodsFor:'arithmetic'!

quo:aNumber
    "Return the integer quotient of dividing the receiver by aNumber with
    truncation towards zero. For Integers this is same as //"

    ^ self // aNumber

! !

!Integer methodsFor:'double dispatching'!

sumFromFraction:aFraction
    "sent when a fraction does not know how to add the recevier, an integer"

    ^ (Fraction numerator:(aFraction numerator
                           + (self * aFraction denominator))
              denominator:aFraction denominator) reduced
!

differenceFromFraction:aFraction
    "sent when a fraction does not know how to subtract the recevier, an integer"

    ^ (Fraction numerator:((self * aFraction denominator) - aFraction numerator)
              denominator:aFraction denominator) reduced
!

productFromFraction:aFraction
    "sent when a fraction does not know how to multiply the recevier, an integer"

    ^ (Fraction numerator:(self * aFraction numerator)
              denominator:aFraction denominator) reduced
! !

!Integer methodsFor:'truncation & rounding'!

ceiling
    "I am my ceiling"

    ^ self
!

floor
    "I am my floor"

    ^ self
!

rounded
    "return the receiver rounded toward the next Integer -
     for integers this is self"

    ^ self
!

truncated
    "return the receiver truncated towards zero - 
     for integers this is self"

    ^ self
! !

!Integer methodsFor:'queries'!

digitLength
    "return the number of bytes needed for the binary representation
     of the receiver"

    ^ (self log:256) ceiling asInteger
!

digitAt:n
    "return the n-th byte of the binary representation"

    |num count|

    num := self.
    count := n.
    [count > 1] whileTrue:[
        num := num // 256.
        count := count - 1
    ].
    ^ num \\ 256
!

isInteger
    "return true, if the receiver is some kind of integer number"

    ^ true
! !

!Integer methodsFor:'misc math'!

factorial
    "return 1*2*3...*self"

    (self > 1) ifTrue:[
        ^ self * (self - 1) factorial
    ].
    ^ self
!

gcd:anInteger
    "return the greatest common divisor (Euclid's algorithm)"

    |ttt selfInteger temp|

    ttt := anInteger.
    selfInteger := self.
    [ttt ~~ 0] whileTrue:[
        temp := selfInteger \\ ttt.
        selfInteger := ttt.
        ttt := temp
    ].
    ^ selfInteger
!

lcm:anInteger
    ^(self * anInteger) abs // (self gcd: anInteger)
!

fib
    "dont use this method if you need fibionacci numbers -
     this method is for benchmarking purposes only.
     (use fastFib instead and dont ever try 60 fib ...)"

    (self > 1) ifTrue:[
        ^ (self - 1) fib + (self - 2) fib
    ].
    ^ 1

    "Time millisecondsToRun:[30 fib]"
!

fastFib
    "this method just to show how a changed algorithm can
     change things much more drastic than tuning ...
     (compare 30 fib with 30 fastFib / dont even try 60 fib)"

    |fib|

    self <= 1 ifTrue:[^ 1].

    FibCache isNil ifTrue:[
        FibCache := OrderedCollection new
    ].
    FibCache size >= self ifTrue:[
        ^ FibCache at:self
    ].
    fib := (self - 2) fastFib + (self - 1) fastFib.

    FibCache grow:self.
    FibCache at:self put:fib.
    ^ fib

    "Time millisecondsToRun:[30 fastFib]"
!

acker:n
    "return the value of acker(self, n)"

    (self == 0) ifTrue:[^ n + 1].
    (n == 0) ifTrue:[^ (self - 1) acker: 1].
    ^ (self - 1) acker:(self acker:(n - 1))

    "3 acker:2"
! !

!Integer methodsFor:'coercing and converting'!

asFraction
    "return a Fraction with same value as receiver"

    ^ Fraction numerator:self denominator:1
!

asInteger
    "return the receiver truncated towards zero - 
     for integers this is self"

    ^ self
! !

!Integer methodsFor:'printing & storing'!

storeString
    "return a string for storing - printString will do"

    ^ self printString
!

printString
    "return a string representation of the receiver"

    ^ self printStringRadix:10
!

radixPrintStringRadix:aRadix
    "return a string representation of the receiver in the specified
     radix; prepend XXr to the string"

    ^ (aRadix printString) , 'r', (self printStringRadix:aRadix)

    "31 radixPrintStringRadix:2 "
    "31 radixPrintStringRadix:3 "
    "31 radixPrintStringRadix:36 "
!

printStringRadix:aRadix
    "return a string representation of the receiver in the specified
     radix (without the initial XXr)"

    |leftPart|

    (self = 0) ifTrue:[^ '0'].
    (self < 0) ifTrue:[
        ^ '-' , (self negated printStringRadix:aRadix)
    ].
    leftPart := self // aRadix.
    (leftPart ~= 0) ifTrue:[
        ^ (leftPart printStringRadix:aRadix) copyWith:(Character digitValue:(self \\ aRadix))
    ].
    ^ (Character digitValue:self) asString
!

printStringRadix:aRadix size:sz fill:fillCharacter
    "return a string representation of the receiver in the specified
     radix. The string is padded on the left with fillCharacter to make
     its size as specified in sz."

     |s|

    s := self printStringRadix:aRadix.
    s size < sz ifTrue:[
        s := ((String new:(sz - s size)) atAllPut:fillCharacter) , s
    ].
    ^ s

    "1024 printStringRadix:16 size:4 fill:$0"
! !

!Integer class methodsFor:'instance creation'!

readFrom:aStream radix:radix
    "return the next Integer from the (character-)stream aStream in radix;
     (assumes that the initial XXR has already been read)
     no whitespace-skipping; returns 0 if no number available"

    |nextChar value|

    nextChar := aStream peek.
    value := 0.
    [nextChar notNil and:[nextChar isDigitRadix:radix]] whileTrue:[
        value := value * radix + nextChar digitValue.
        nextChar := aStream nextPeek
    ].
    ^ value
!

readFrom:aStream
    "return the next Integer from the (character-)stream aStream,
     handling initial XXr for arbitrary radix numbers and initial
     sign.
     skipping all whitespace first; return nil if no number"

    |nextChar value negative|

    nextChar := aStream skipSeparators.
    (nextChar == $-) ifTrue:[
        negative := true.
        nextChar := aStream nextPeek
    ] ifFalse:[
        negative := false
    ].
    nextChar isDigit ifFalse:[ ^ nil].
    value := Integer readFrom:aStream radix:10.
    nextChar := aStream peek.
    ((nextChar == $r) or:[ nextChar == $R]) ifTrue:[
        aStream next.
        value := Integer readFrom:aStream radix:value
    ].
    negative ifTrue:[
        ^ value negated
    ].
    ^ value
! !

!Integer methodsFor:'benchmarking'!

sieve
    "sieve the primes self times"

    |num i k prime count flags time|

    num := 8191.
    flags := Array new:num.

    Transcript show:'Sieve running ...'.
    Transcript cr.

    time := Time millisecondsToRun:[
        self timesRepeat:[
            count := 0.
            flags atAllPut:1.
            i := 1.
            num timesRepeat:[
                (flags at:i) == 1 ifTrue:[
                    prime := i + i + 3.
                    k := i + prime.
                    [k <= num] whileTrue:[
                        flags at:k put:0.
                        k := k + prime
                    ].
                    count := count + 1
                ].
                i := i + 1
            ].
        ].
    ].
    Transcript show:'Sieve in Smalltalk: '.
    Transcript show:self printString. 
    Transcript showCr:' iteration(s).'.
    Transcript show:'found '. 
    Transcript show:count printString. 
    Transcript showCr:' primes.' .
    Transcript show:'time per run: '. 
    Transcript show:(time / self) printString. 
    Transcript showCr:' ms.'

    "1 sieve"
!

sieveWithIntegers
    "sieve the primes self times"

    |num        "<SmallInteger>"
     i          "<SmallInteger>"
     k          "<SmallInteger>"
     prime      "<SmallInteger>"
     count      "<SmallInteger>"
     flags time|

    num := 8191.
    flags := Array new:num.

    Transcript show:'Sieve running ...'.
    Transcript cr.

    time := Time millisecondsToRun:[
        self timesRepeat:[
            count := 0.
            flags atAllPut:1.
            i := 1.
            num timesRepeat:[
                (flags at:i) == 1 ifTrue:[
                    prime := i + i + 3.
                    k := i + prime.
                    [k <= num] whileTrue:[
                        flags at:k put:0.
                        k := k + prime
                    ].
                    count := count + 1
                ].
                i := i + 1
            ].
        ].
    ].
    Transcript show:'Sieve in Smalltalk: '.
    Transcript show:self printString. 
    Transcript showCr:' iteration(s).'.
    Transcript show:'found '. 
    Transcript show:count printString. 
    Transcript showCr:' primes.' .
    Transcript show:'time per run: '. 
    Transcript show:(time / self) printString. 
    Transcript showCr:' ms.'

    "1 sieveWithIntegers"
!

recur1:num
    "actual recursion method for recur1"

    (num = 0) ifTrue:[^ self].
    self recur1:(num - 1).
    ^ self recur1:(num - 1)
!

recur1
    "lots of recursion for testing send with arg"

    |t|

    t := Time millisecondsToRun:[
        1 recur1:15
    ].
    Transcript showCr:(t printString)

    "1 recur1"
!

recur2
    "lots of recursion for testing send without arg"

    (self > 0) ifTrue:[
        (self - 1) recur2.
        ^ (self - 1) recur2
    ]

    "Transcript showCr:(
        Time millisecondsToRun:[
            15 recur2
        ]
     ) printString"
!

countDown
    |t index|

    t := Time millisecondsToRun:[
        index := 100000.
        [index > 0] whileTrue:[
            index := index - 1
        ].
    ].
    Transcript showCr:(t printString)

    "1 countDown"
!

countDown2
    |t|

    t := Time millisecondsToRun:[
        |index|

        index := 100000.
        [index > 0] whileTrue:[
            index := index - 1
        ].
    ].
    Transcript showCr:(t printString)

    "1 countDown2"
!

noop
    ^ self
!

send:num
    "lots of message sends"

    |t|

    t := Time millisecondsToRun:[
        num timesRepeat:[
            self noop
        ].
    ].
    Transcript showCr:(t printString)

    "1 send:100000"
!

memory
    "lots of memory allocation"

    |t|

    t := Time millisecondsToRun:[
        self timesRepeat:[
            Array new:500
        ].
    ].
    Transcript showCr:(t printString)

    "10000 memory"
!

benchArithmetic
    "arithmetic speed bench"

    |p n m t|

    n := 3.0.
    m := 5.5.

    t := Time millisecondsToRun:[
        self timesRepeat:[
            p := 5 / n + m
        ]
    ].
    Transcript showCr:(t printString)

    "10000 benchArithmetic"
!

sumTo
    |val|

    100 timesRepeat:[
        val := 0.
        1 to:10000 do:[:i |
            val := val + i
        ]
    ].
    "Time millisecondsToRun:[1 sumTo]"
!

fastSumTo
    |val i|

    100 timesRepeat:[
        val := 0.
        i := 1.
        [i <= 10000] whileTrue:[
            val := val + i.
            i := i + 1
        ].
    ].
    "Time millisecondsToRun:[1 fastSumTo]"
!

nestedLoop
    |i|

    100 timesRepeat:[
        i := 0.
        1 to:100 do:[:l1 |
            1 to:100 do:[:l2 |
                i := i + 1
            ]
        ]
    ]
    "Time millisecondsToRun:[1 nestedLoop]"
!

atAllPut
    |vec t|

    vec := Array new:100000.
    t := Time millisecondsToRun:[
        1 to:100000 do:[:i |
            vec at:i put:7
        ]
    ].
    ^ t

    "1  atAllPut"
!

atAllPut2
    |array t|

    array := Array new:100000.
    t := Time millisecondsToRun:[
        1 to:100000 do:[:i |
            array at:i put:7
        ]
    ].
    ^ t

    "1  atAllPut2"
!

sumAll 
    |vec t s|

    vec := Array new:100000.
    1 to:100000 do:[:i |
        vec at:i put:7
    ].
    s := 0.
    t := Time millisecondsToRun:[
        1 to:100000 do:[:i |
            s := s + (vec at:i)
        ]
    ].
    ^ t

    "1  sumAll"
!

sumAll2 
    |array t s|

    array := Array new:100000.
    1 to:100000 do:[:i |
        array at:i put:7
    ].
    s := 0.
    t := Time millisecondsToRun:[
        1 to:100000 do:[:i |
            s := s + (array at:i)
        ]
    ].
    ^ t

    "1  sumAll2"
! !