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

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!

  • Comment on Re^4: how to speed up program dealing with large numbers?

Replies are listed 'Best First'.
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.
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

    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.