hg/stx-libbasic: comparison Integer.st

equal deleted inserted replaced

-:43a439f72615
+:c7b914e6ed2b
 "Modified: 18.7.1996 / 13:08:16 / cg"
 !
 binco:kIn
+"an alternative name for the binomial coefficient for squeak compatibility"
 ^ self binomialCoefficient:kIn
+"Modified: / 17-08-2010 / 17:29:07 / cg"
 !
 binomialCoefficient:kIn
 "The binomial coefficient
 !
 fib_helper
 "compute the fibionacci number for the receiver.
-	Fib(n) = Fib(n-1) + Fib(n-2)
+Fib(n) = Fib(n-1) + Fib(n-2)
 Knuth:
-	Fib(n+m) = Fib(m) * Fib(n+1) + Fib(m-1) * Fib(n)
+Fib(n+m) = Fib(m) * Fib(n+1) + Fib(m-1) * Fib(n)
 This is about 3 times faster than fib_iterative.
 "
 |fibUsingDict dict|
 dict := Dictionary new:100.
 fibUsingDict := [:x |
-	|n fib fibN fibNp1 fibNm1 fibXm1 fibXm2 fibXp1|
+|n fib fibN fibNp1 fibNm1 fibXm1 fibXm2 fibXp1|
-	x <= 30 ifTrue:[
+x <= 30 ifTrue:[
-		"/ 0 1 2 3 4 5 6  7  8  9 10 11  12  13  14  15  16   17   18   19   20    21    22    23    24    25     26     27     28     29     30
+"/ 0 1 2 3 4 5 6  7  8  9 10 11  12  13  14  15  16   17   18   19   20    21    22    23    24    25     26     27     28     29     30
-	    fib := #(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
+fib := #(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
-		     ) at:x
+) at:x
-	] ifFalse:[
+] ifFalse:[
-	    fib := dict at:x ifAbsent:nil.
+fib := dict at:x ifAbsent:nil.
-	    fib isNil ifTrue:[
+fib isNil ifTrue:[
-		fibXm1 := dict at:(x-1) ifAbsent:nil.
+fibXm1 := dict at:(x-1) ifAbsent:nil.
-		fibXm1 notNil ifTrue:[
+fibXm1 notNil ifTrue:[
-		    fibXm2 := dict at:(x-2) ifAbsent:nil.
+fibXm2 := dict at:(x-2) ifAbsent:nil.
-		    fibXm2 notNil ifTrue:[
+fibXm2 notNil ifTrue:[
-			fib := fibXm1 + fibXm2.
+fib := fibXm1 + fibXm2.
-		    ] ifFalse:[
+] ifFalse:[
-			fibXp1 := dict at:(x+1) ifAbsent:nil.
+fibXp1 := dict at:(x+1) ifAbsent:nil.
-			fibXp1 notNil ifTrue:[
+fibXp1 notNil ifTrue:[
-			    fib := fibXp1 - fibXm1.
+fib := fibXp1 - fibXm1.
-			]
+]
-		    ]
+]
-		].
+].
-		fib isNil ifTrue:[
+fib isNil ifTrue:[
-		    n := x // 2.
+n := x // 2.
-		    x odd ifTrue:[
+x odd ifTrue:[
-			"/ m is set to n+1; therefore:
+"/ m is set to n+1; therefore:
-			"/ Fib(x) = Fib(n+n+1)      ; x odd; setting n = (x-1)/2
+"/ Fib(x) = Fib(n+n+1)      ; x odd; setting n = (x-1)/2
-			"/ using Knuth:
+"/ using Knuth:
-			"/ Fib(n+n+1) = Fib(n+1) * Fib(n+1) + Fib(n+1-1) * Fib(n)
+"/ Fib(n+n+1) = Fib(n+1) * Fib(n+1) + Fib(n+1-1) * Fib(n)
-			"/            = (Fib(n+1) ^ 2) + (Fib(n) ^ 2)
+"/            = (Fib(n+1) ^ 2) + (Fib(n) ^ 2)
-			fibN   := fibUsingDict value:n.
+fibN   := fibUsingDict value:n.
-			fibNp1 := fibUsingDict value:(n+1).
+fibNp1 := fibUsingDict value:(n+1).
-			fib := fibN squared + fibNp1 squared
+fib := fibN squared + fibNp1 squared
-		    ] ifFalse:[
+] ifFalse:[
-			"/ as
+"/ as
-			"/    Fib(n+1) = Fib(n) + Fib(n-1)
+"/    Fib(n+1) = Fib(n) + Fib(n-1)
-			"/ therefore:
+"/ therefore:
-			"/    Fib(n) = Fib(n+1) - Fib(n-1)
+"/    Fib(n) = Fib(n+1) - Fib(n-1)
-			"/ and, since n is even, n+1 and n-1 are odd, and can be computed as above.
+"/ and, since n is even, n+1 and n-1 are odd, and can be computed as above.
-			"/ This gives us:
+"/ This gives us:
-			"/    Fib(x) = Fib(x+1) - Fib(x-1)      ; x even; setting n = x/2
+"/    Fib(x) = Fib(x+1) - Fib(x-1)      ; x even; setting n = x/2
-			"/           = Fib(n+n+1) - Fib(n+n-1)
+"/           = Fib(n+n+1) - Fib(n+n-1)
-			"/           = Fib(n+n+1) - Fib((n-1)+(n-1)+1)
+"/           = Fib(n+n+1) - Fib((n-1)+(n-1)+1)
-			"/           = ((Fib(n+1)^2) + (Fib(n)^2)) - ((Fib((n-1)+1)^2) + (Fib((n-1))^2))
+"/           = ((Fib(n+1)^2) + (Fib(n)^2)) - ((Fib((n-1)+1)^2) + (Fib((n-1))^2))
-			"/           = (Fib(n+1)^2) + (Fib(n)^2) - (Fib(n)^2) - (Fib((n-1))^2)
+"/           = (Fib(n+1)^2) + (Fib(n)^2) - (Fib(n)^2) - (Fib((n-1))^2)
-			"/           = (Fib(n+1)^2) - (Fib((n-1))^2)
+"/           = (Fib(n+1)^2) - (Fib((n-1))^2)
-			fibNm1 := fibUsingDict value:(n-1).
+fibNm1 := fibUsingDict value:(n-1).
-			fibNp1 := fibUsingDict value:(n+1).
+fibNp1 := fibUsingDict value:(n+1).
-			fib := fibNp1 squared - fibNm1 squared
+fib := fibNp1 squared - fibNm1 squared
-		    ].
+].
-		].
+].
-		dict at:x put:fib.
+dict at:x put:fib.
-	    ]
+]
-	].
+].
-	fib
+fib
 ].
 ^ fibUsingDict value:self
 "the running time is mostly dictated by the LargeInteger multiplication performance...
 Time millisecondsToRun:[400000 fib_helper]    6084
 1 to:100 do:[:i | self assert:(i fib_iterative = i fib_helper) ]
 1 to:100 do:[:i | self assert:(i fib_iterative = i fib) ]
 "
+"Modified: / 17-08-2010 / 17:29:34 / cg"
 !
 gcd:anInteger
 "return the greatest common divisor of the receiver and anInteger.
 Euclids & Knuths algorithm."
 b := self highBit.
 rem := 1 bitShift:b.
 result := LargeInteger basicNew numberOfDigits:(b // 8)+1.
 b := b+1.
 [b > 0] whileTrue:[
-	rem >= self ifTrue:[
+rem >= self ifTrue:[
-	    rem := rem -= self.
+rem := rem -= self.
-	    result digitBytes bitSetAt:b.
+result digitBytes bitSetAt:b.
-	].
+].
-	rem := rem mul2.
+rem := rem mul2.
-	b := b - 1.
+b := b - 1.
 ].
 ^ result compressed.
 "
 333 integerReciprocal                (2 raisedTo:18) // 333
 393 integerReciprocal
 8 integerReciprocal
 15 integerReciprocal
 15112233445566 integerReciprocal
 10239552311579 integerReciprocal
 "
-"Modified: / 3.5.1999 / 14:27:18 / stefan"
+"Modified: / 03-05-1999 / 14:27:18 / stefan"
+"Modified: / 17-08-2010 / 17:30:22 / cg"
 !
 integerSqrt
 "newton's method to get the largest integer which is less or equal to the
 receiver's square root.
 ! !
 !Integer class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.250 2010-08-17 15:28:16 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.251 2010-08-17 15:32:31 cg Exp $'
 !
 version_CVS
-^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.250 2010-08-17 15:28:16 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.251 2010-08-17 15:32:31 cg Exp $'
 ! !
 Integer initialize!

changeset 13023	c7b914e6ed2b
parent 13022	43a439f72615
child 13367	fa81e6298411