[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
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
More information about the Squeak-dev
mailing list
|