[squeak-dev] Faster fibonacci

tim Rowledge tim at rowledge.org
Tue Apr 16 19:45:46 UTC 2019


I've been involved in a long and sometimes weird discussion on the RaspberryPi forums about fibonacci implementations in different languages and using assorted algorithms. I'd never really thought about alternatives to  recursive approaches before but it turns out there is massively faster way. Clearly, this is not to replace the benchFib code since that has a specific use, but if anyone with an interest in numerics wants a faster way to generate fib(8577) for example, this is how - 

Integer >> fastDoublingFib
"derived from https://www.nayuki.io/page/fast-fibonacci-algorithms"
"(1 to: 20) collect:[:i| i fastDoublingFib]"
"testing a quite large one - "
"8577 fastDoublingFib= 13724780954457889052017147206983806244049002655849289934662148526555403650297300643609932653364630032094175733360509578504423049114004867523161091564824674600978308740378989479162611031273424686573759784740689516901416473328655422390895971263265867635819510949686102571388751758998017349379498918930220900180038324615253426530740473855269056304380498630108126734047701362218655030270360608989081398866489746698916626888016696892691933237089180504631788915650757757515944644732966345269202761471025651071790297611079540881155092137592980230998234868586211881093892491570520577408961869977892273540956424095750855208529072246641778982103984467921868950012668004047986803017482248992968482737462668300684879633714025755790485860328854796518843956263863014632532331145699658530054942590047273403691531821918862996422405159427262092477196755988981309029424760342802374213122162727840557722145891090413688461745240415668189577836068480363407847582529735341950500636735281963089675493707159434777756081146452522323681782226760627277553296721358921412115264845467834979154061137421532609247762981818564578019888974692581079593575783553856910367568474613323528337733872069223030834774749130478360574004172522316484339530942110067893000847800932306298725285623628731149337468217751734165148732164148285915275115006479682658150442259002271790547596033006363411193653337536041106069912826015502035140618407668385378737477702597473151509972754111640855347958033314453349633268543893894677097708945041254623018915871109789412793709229204261914803477697183287924195770678873001065036313926288444791424871512110658175954743584548831946767673488152740675550518235698898217693311515366329280005757014637854214769152690638778904780724293185353992279724740604674926819294787586671833537117545443846365508358918882"
	| a b c |
	a :=  0.
	b := 1.
	self highBit to: 1 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]
		].
	^a
I bet it could be sped up more, but a simply spyOn run just allocated all the primitive time to delay waiting. Didn't we improve that some time ago?

tim
--
tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
Strange OpCodes: BYEBYE: Store in Write-Only Storage




More information about the Squeak-dev mailing list