[squeak-dev] Faster fibonacci

Levente Uzonyi leves at caesar.elte.hu
Wed Apr 17 11:26:08 UTC 2019

On Tue, 16 Apr 2019, tim Rowledge wrote:

> 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?

That's some pretty nifty code. Other than the typical tricks, you 
can't make it any quicker for larger receivers.
What are these typical tricks?
- inlining methods
- decreasing the number of temporaries needed
- reordering temporaries so that the more frequently used ones use 
- declare all temporaries at the method level so that the compiler can 
skip a few bytecodes setting their values to nil in each loop

But as the receiver gets larger, the LargeInteger primitives will dominate 
the run time more and more, so the tricks will have neglibile effect on 

And yes, we do have a better profiler: AndreasSystemProfiler. It hasn't 
been integrated into Squeak yet for some reason, but it's available on 


> 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