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 
registers
- 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 
performance.

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 
SqueakMap.

Levente

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