[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