[squeak-dev] Faster fibonacci
tim Rowledge
tim at rowledge.org
Fri Jul 19 05:21:06 UTC 2019
A small but valuable improvement in the fibonacci algorithm blatantly stolen from a python version by gkreidel on the Pi forums seems to be ~25% faster for 4784969 fibonacci
!Integer methodsFor: 'mathematical functions' stamp: 'tpr 5/6/2019 12:22'!
fibonacci
"derived from https://www.nayuki.io/page/fast-fibonacci-algorithms"
"4784969 fibonacci"
| a b c |
self <= 0 ifTrue: [^0]. "in case somebody tries an inappropriate number"
a := 0.
b := 1.
self highBit to: 2 by: -1 do:[:i||d e|
d := ((b bitShift: 1) - a) * a.
e := a squared + b squared.
a := d.
b := e.
(self bitAt: i) = 1 ifTrue:[
c := a + b.
a := b.
b := c]
].
^self odd
ifTrue:[a squared + b squared]
ifFalse: [((b bitShift: 1) - a) * a]! !
About 75% of time goes on the #squared and 8% on WeakArray finalization.
tim
--
tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
Useful random insult:- A room temperature IQ.
More information about the Squeak-dev
mailing list
|