Talk:Happy numbers: Difference between revisions
Content added Content deleted
(→On caching (and laziness): But just doing one iteration is still better (and I'm now convinced it actually is).) |
(→On caching (and laziness): still I find the "bag" solution finer to me) |
||
| Line 9: | Line 9: | ||
::: However if instead of the "bunch of numbers" you instead store the sum of their squares (which is actually the only thing that matters), you still get more efficient (indeed, you get more efficient in two ways; you need less storage per entry, and you need less entries, because e.g. the cases "4 ones", "4 ones and a zero", "one two", "one two and ten zeroes", etc. all go into the same cache entry). |
::: However if instead of the "bunch of numbers" you instead store the sum of their squares (which is actually the only thing that matters), you still get more efficient (indeed, you get more efficient in two ways; you need less storage per entry, and you need less entries, because e.g. the cases "4 ones", "4 ones and a zero", "one two", "one two and ten zeroes", etc. all go into the same cache entry). |
||
::: However, I now think it would be a saving anyway. The digit square sums tend to be much smaller than the original numbers; indeed, with a 32 bit unsigned int, the largest possible value after one step would be 657 (unless I mis-calculated). If storing the flags in single bits, you'd need just 83 bytes, and lookup would be strictly O(1). Moreover, if you don't have that number in the cache, you have to do this calculation anyway, so you don't lose much time in that case, so the only efficiency loss is for numbers already in the cache, but that's just one iteration (for 32 bit uint in the worst case, 18 divisions, 18 modulo operations, 9 multiplications and 17 additions, if I counted correctly). Moreover the needed memory then goes linear in the number of digits, so even with 64 bits you won't need too much memory. --[[User:Ce|Ce]] 13:30, 7 May 2009 (UTC) |
::: However, I now think it would be a saving anyway. The digit square sums tend to be much smaller than the original numbers; indeed, with a 32 bit unsigned int, the largest possible value after one step would be 657 (unless I mis-calculated). If storing the flags in single bits, you'd need just 83 bytes, and lookup would be strictly O(1). Moreover, if you don't have that number in the cache, you have to do this calculation anyway, so you don't lose much time in that case, so the only efficiency loss is for numbers already in the cache, but that's just one iteration (for 32 bit uint in the worst case, 18 divisions, 18 modulo operations, 9 multiplications and 17 additions, if I counted correctly). Moreover the needed memory then goes linear in the number of digits, so even with 64 bits you won't need too much memory. --[[User:Ce|Ce]] 13:30, 7 May 2009 (UTC) |
||
:::: Likely. However happy numbers seem not to be memory or cpu intensive (even with Smalltalk, which surely is not a "light") I was able to find fastly happy numbers upto 10000 (and not beyond just since I've not changed the constant!), where with "fastly" I mean just the time to output them; "no time" among one output line and the other one ("no time" meaning: far less than 1s, i.e. less than a human can perceive like a "estimable by eye" duration). --[[User:ShinTakezou|ShinTakezou]] 17:19, 7 May 2009 (UTC) |
|||