Re^3: how to speed up program dealing with large numbers?

An array would be better suited than a hash since we're dealing with non-negative integer indexes.

Even in this specific case, the difference in either performance or memory is so marginal as to be essentially unmeasurable.

For 1..1000, both take around 1.3 seconds and negligable amounts of memory. Where the original implementation would take ~~months if not years~~ longer than the universe has existed!

But using a hash for caching makes far more sense because of its generality.

Giving up that generality to move from being ~~15,000,000~~ 1e+196 times faster to being ~~15,000,001~~ 1e+196 + 1 times faster is simply pointless. To put that into perspective, it means your changes on top of mine will make a difference of approximately:

0.00000000000000000000000000000000000000000000000000000000000000000000
+000000000000000000000000000000000000000000000000000000000000000000000
+000000000000000000000000000000000000000000000000000000000999999999999
+999999999999999999999999999999999999999999999999999999999999999999999
+999999999999999999999999999999999999999999999999999999999999999999999
+999999999999999999999999999999999999999999999900000000000000000000000
+000000000000000000000000000000000000000000000000000000000000000000000
+000000000000000000000000000000000000000000000000000000000000000000000
+000000000000000000000000000000000009999999999999999999999999999999999
+999999999999999999999999999999999999999999999999999999999999999999999
+999999999999999999999999999999999999999999999999999999999999999999999
+999999999999999999999999000000000000000000000000000000000000000000000
+000000000000000000000000000000000000000000000000000000000000000000000
+000000000000000000000000000000000000000000000000000000000000000000000
+0000000000001%
[download]

Worth the effort?

Sub calls are expensive in Perl, and there's no need for recursion here, so let's eliminate them:

Again, an utterly pointless exercise.

When performing the range 1 .. 1000, with the cached version the fib function is called 3005 times. That's twice for each iteration from the main loop, leaving 1 recursion per iteration. Compare that to the original implementation that would call fib() ~1e200 times. That's:

100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00
+0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
+,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
+000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
[download]

So any additional savings are so utterly marginal as to be completely unmeasurable.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"I'd rather go naked than blow up my ass"

Comment on Re^3: how to speed up program dealing with large numbers? Select or Download Code

Replies are listed 'Best First'.
Re^4: how to speed up program dealing with large numbers? by Solarplight (Sexton) on Mar 22, 2010 at 04:36 UTC
Absolutely no doubt that using the hash is a million time better than my original implementation. In my original if you started at the 20th value and just did a range of 5 it would take forever. With the hash I've barely been able to get it to hang up more than a second or two, and thats with a range of 100.	[reply]
Re^4: how to speed up program dealing with large numbers? by ikegami (Patriarch) on Mar 22, 2010 at 05:36 UTC
Worth the effort? What effort? I would have used an array from the start, meaning it take extra effort to use the hash version. Besides, we're talking of a 5 character difference. Compare that to the original implementation Why? When benchmarking video cards, you don't compare them to a CGA video card, you compare them to each other.	[reply]
Re^5: how to speed up program dealing with large numbers? by Anonymous Monk on Mar 22, 2010 at 15:14 UTC
What effort? The effort you made trying to think of something, anything, to post. I would have used an array from the start, And because you do it wrong, everybody should. When benchmarking Your micro-optimisations would still not make a blind bit of difference.	[reply]
Re^6: how to speed up program dealing with large numbers? by ikegami (Patriarch) on Mar 22, 2010 at 15:51 UTC
Please take offtopic personal messages offline	[reply]
Re^4: how to speed up program dealing with large numbers? by SuicideJunkie (Vicar) on Mar 22, 2010 at 22:01 UTC
Just because you've made your algorithm 1e200 times faster does not mean that you can't improve it any further. It just means you are in a whole new performance scope. The other week, I moved from an O(n^2) to an O(n) algorithm and saved an arbitrarily large amount of time. (On the old "patience" sample data, it was a 30,000% speedup after the extra overhead costs. On the new "quick" sample data it would have been a 120,000% improvement. There is no sample big enough to qualify as "patience" anymore.) Then the next week, I made another 2x improvement. If you think about it as running in 0.0004 time vs 0.0008 time, you're playing to the pessimist in you with math and psychology tricks. That extra 2x improvement was still well worth doing!	[reply]
Re^5: how to speed up program dealing with large numbers? by BrowserUk (Patriarch) on Mar 22, 2010 at 22:07 UTC
That extra 2x improvement was still well worth doing! If there were a 2X improvement, or even a 0.2X improvement it would be worth considering the trade off against the loss of generality, but there isn't. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "I'd rather go naked than blow up my ass"	[reply]
Re^5: how to speed up program dealing with large numbers? by BrowserUk (Patriarch) on Mar 28, 2010 at 04:22 UTC
you're playing to the pessimist in you with math and psychology tricks Sorry to come back to this, but I just watched a rather silly, but never the less interesting program that just brought this discussion flooding back. You can catch the program here, though that link might only work in the UK. Skip directly to the segment starting at 12:35 seconds in. To summarise for those that cannot watch, (or can't be bothered), the discussion is about just how tiny atoms are. They say & do some simple, but evocative things, to try and convey the scale of large and small. The one that stood out for me was this. The number of atoms in the entire universe is: one followed by 80 zeros. That's 1e80. Or 100 million, trillion, trillion, trillion, trillion, trillion, trillion. `100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00 +0,000,000,000,000,000,000,000,000,000` [download] That is described as "an unimaginably huge number". Now contrast that with the 1e200 you quoted from my post. And then contrast that, with your reference of 120,000% + 2X.. People in general, and mathematicians in particular, simply have no concept of how small a difference 1/1e196 is. I tried to think of a way to put that into some perspective that most people would understand. People think that they have some concept of how far it is from here to the moon. 1/4 of 1 million miles. Easy to say, but still very few people have any real feel for how far that is. If we travelled to the moon by car (at 60mph), it would take not your worst daily commute of 2 hours each way; or your longest every fly-drive holiday of 3,500 miles in 14 days; it would take 6 months. If you flew in the fastest transport most of us will every experience--a jet liner--it would take not a intercity 1 hour, nor an inter-continent 8 hours; nor even a round-world, 24 hours. It would take 17 days! So, if we take the smallest distance most people can truly envisage--1 millimeter--and compare it to the distance between the earth and the moon, we get 1/4e12. So the difference of 1e196, on the scale of the distance from here to the moon is 1/1e184 of a millimeter. Still too small to envisage. So, lets expand 1 millimeter to be the distance from here to the Moon, Now 1 millimeter is 1/1e172 of that expanded millimeter. Repeat that process--expanding 1 millimeter to be the ~400,000 kilometers from the earth to the moon--14 times more, and you end up with close to 1e196. And does that make things any clearer? Does it point out just how minuscule the difference between 1e196 and 1e196+1 really is? And the answer is a resounding : "NO!". My point is, that what you call "psychology tricks", is quite the reverse. By elaborating these numbers out in their unadulterated fullness, I'm not trying to pull the wool over anyones eyes. Quite the reverse. I'm attempting to make people realise just how small a difference we are discussing. It is all very well talking relativistically, talking of benchmarking CGA screens against XVGA, but that is comparing the thickness of a human hair to the length of your street; not the diameter of an atom to the size of the Universe. And even the latter is humongously large relative to the difference using an array rather than a hash for caching makes, over using caching in the first place. If you expanded an atom to the size of the Universe, the difference would be less that two atoms in that re-scaled universe. I do not employ "psychology tricks", I attempt to make people think about the numbers that get banded about so willy-nilly. With the operative word in that sentence being: think! Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "I'd rather go naked than blow up my ass"	[reply] [d/l]