Talk:Rare numbers: Difference between revisions
(→21+ digit rare numbers: Compare C++ and goTurbo) |
(→21+ digit rare numbers: Responded to Nigel.) |
||
Line 628: | Line 628: | ||
I think this demonstrates that the task should require at least the first 63 Rare numbers!!! |
I think this demonstrates that the task should require at least the first 63 Rare numbers!!! |
||
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:22, 19 March 2020 (UTC) |
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:22, 19 March 2020 (UTC) |
||
::::LOL, the Go version is even faster on your i5 than it is on my i7, and only about 50% behind mingw! I imagine you're running it on Windows 10 whereas I'm using Ubuntu 18.04 but that shouldn't make much difference. Probably should have bought an i7 with a higher basic clock speed as performance can be a bit disappointing at times. |
|||
::::The stretch goal is already open-ended and Enter your username has certainly gone well beyond the call of duty there :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 14:32, 19 March 2020 (UTC) |
|||
::::: I find it hard to believe that clang++ could be 3 times faster than g++ (though you can get some strange results with these CPU-intensive tasks) and, although I no longer have an up to date Windows machine, on past form I'd be surprised if Visual C++ were any faster than g++ itself. Enter your username may be able to confirm the position there. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:53, 20 December 2019 (UTC) |
::::: I find it hard to believe that clang++ could be 3 times faster than g++ (though you can get some strange results with these CPU-intensive tasks) and, although I no longer have an up to date Windows machine, on past form I'd be surprised if Visual C++ were any faster than g++ itself. Enter your username may be able to confirm the position there. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:53, 20 December 2019 (UTC) |
Revision as of 14:32, 19 March 2020
comments concerning interesting observations from an webpage
(The author's webpage, the last URL reference from this task's preamble, re-shown below:)
(a URL reference):
- author's website: rare numbers by Shyam Sunder Gupta. (lots of hints and some observations).
I was considering adding checks (to the REXX program) to assert that for:
- when the number of digits in a rare number is even, the sum must be divisible by 11, and
- when the number of digits in a rare number is odd, the difference must be divisible by 9.
n-r is divisible by 9 for all Rare numbers. n-r is also divisible by 99 when the number of digits is odd. (see Talk:Rare_numbers#30_mins_not_30_years)--Nigel Galloway (talk) 13:48, 21 September 2019 (UTC)
30 mins not 30 years
If Shyam Sunder Gupta has really spent 30 years on this he should have stayed in bed. Let me spend 30mins on it. The following took 9mins so any questions and I have 21mins to spare.
Let me consider n-r=l for a 2 digit number ng n<g. Then l=(10g+n)-(g+10n)=9(g-n) where n is 0..8 and g is 1..9. l is one of 9 18 27 36 45 54 63 72 81. l must be a perfect square so only 9 36 and 81 are of interest. 9 -> ng=89 78 67 56 45 34 23 12 01 36-> ng=59 48 37 26 15 04 81-> ng=09 For each of these candidate ng I must determine if ng+gn is a perfect square. 09+90 99 n 59+95 154 n 48+84 132 n 37+73 110 n 26+62 114 n 15+51 66 n 04+40 44 n 89+98 187 n 78+87 165 n 67+76 143 n 56+65 121 y 45+54 99 n 34+43 77 n 23+32 55 n 12+21 33 n 01+10 11 n From which I see that 65 is the only Rare 2 digit number. I love an odd number of digits. Let me call the 3 digit number nxg. l=(100g+10x+n)-(g+10x+100n). x disappears and I am left with 99(g-n). None of 99 198 297 396 495 594 693 792 or 894 are perfect squares. So there are no Rare 3 digit numbers. At 4 I begin to think about using a computer. Consider nige. l=(1000e+100g+10i+n)-(e+10g+100i+1000n). I need a table for l as above for 9(111(e-n)+10(g-i)) where n<=e and if n=e then i<g. Before turning the computer on I'll add that for 5 digits nixge l=(10000e+1000g+100x+10i+n)-(e+10g+100x+1000i+10000n). x disappears leaving 99(111(e-n)+10(g-i))
--Nigel Galloway (talk) 13:34, 12 September 2019 (UTC)
- I have turned the computer on and produced a solution using only the above and nothing from the referenced website which completes in under a minute. The reference is rubbish, consider removing it--Nigel Galloway (talk) 10:42, 18 September 2019 (UTC)
- Rubbish or not, is there anything on the referenced (Gupta's) website that is incorrect? The properties and observations is what the REXX solution used (and others have as well) to calculate rare numbers, albeit not as fast as your algorithm. I have no idea how long Shyam Sunder Gupta's program(s) executed before it found eight rare numbers (or how much virtual memory it needed). Is the F# algorithm suitable in finding larger rare numbers? I suspect (not knowing F#) that virtual memory may become a limitation. Eight down, seventy-six more to go. -- Gerard Schildberger (talk) 18:18, 18 September 2019 (UTC)
- So is the task now to replicate [[1]]? This may not be reasonable for a RC task as I now discuss.
Why have you "no idea how long Shyam Sunder Gupta's program(s) executed before it found eight rare numbers"? On the webpage it says "the program has been made so powerful that all numbers up to 10^14 can be just checked for Rare numbers in less than a minute". This implies that it can search 10^13 in 5 secs. I believe this. The problem with the webpage is not that it is wrong, but that it is disingenuous. I estimate that the following is achievable:
10^13 -> 5 secs;
10^15 -> 60 secs;
10^17 -> 20 mins;
10^19 -> 7 hours;
10^21 -> 6 days;
10^23 -> 4 months.
I would say that 10^17 is reasonable for a RC task and is in line with the timings given on the webpage. Those who have recently obtained an 8th. generation i7 might want to observe that there is an obvious multithreading strategy and might want to prove that Goroutines are more than a bad pun on coroutines, as a suitable punishment for making me envious. (Warning, from my experience of i7s it might be wise to take it back to the shop and have water cooling installed before attempting to run it for a day and a half on full throttle). I remain to be convinced that these benchmarks are achieved by the Fortran, Ubasic programs on the webpage, or can be achieved in this task using the methods described on the webpage.
It is necessary to distinguish the algorithm I describe above from the F# implementation on the task page. The algorithm can be written to require very little memory. Obviously the F# as it stands calculates all candidates before checking them and this list grows with increasing number of digits. It is more than adequate for the current task, and I anticipate little difficulty in accommodating reasonable changes to make the task less trivial as layed out above--Nigel Galloway (talk) 14:01, 20 September 2019 (UTC)
- So is the task now to replicate [[1]]? This may not be reasonable for a RC task as I now discuss.
- Obviously, this task's requirement is not to replicate the list of 84 rare numbers on [Shyam Sunder Gupta's webpage: a list of 84 rare numbers]. The task requirements have not changed: find and show the first 5 rare numbers. The last two requirements are optional. Any hints and properties can be used as one sees fit. -- Gerard Schildberger (talk) 17:55, 20 September 2019 (UTC)
- Well, I have to admit that Nigel's (n-r) approach is considerably faster than what SSG has published as I've just added a second Go version which finds the first 25 Rare numbers (up to 15 digits) in about 42 seconds, albeit on my Core i7 which is kept cool when hitting turbo mode by a rather noisy fan.
- Although I don't doubt SSG's claims (he is presumably a numerical expert), he must be using much more sophisticated methods than he has published to achieve those sort of times on antique hardware.
- Incidentally, I regard it as bad form to use concurrent processing (i.e. goroutines) in RC tasks unless this is specifically asked for or is otherwise unavoidable (for processing events in some GUI package for example). It is difficult for languages which don't have this stuff built in to compete and it may disguise the usage of what are basically poor algorithms. --PureFox (talk) 23:04, 24 September 2019 (UTC)
A few more mins.
Above I considered n-r=L and investigated the nature of L. It is difficult to estimate complexity with increasing number of digits for this algorithm because: it depends on the number of L which happen to be a perfect square, which is neither random nor easy to predict; each L which is a perfect square expands into varying number of r. At first sight n+r=H does not look promising. For the number n....g n+g may take the values 1 to 18 rather than 1 to 9 for n-g and for an odd number of digits x doesn't disappear, rather it creates 10 times the number of possibilites.
For a rare number H-L=(n+r)-(n-r)=2r which implies that for a Rare number H and L must both be odd or even. From the lists H and R I can produce all the candidates for r. n is H-r therefore I must simply determine for each candidate is r H-r reversed (see C++ on the task page). The nice thing is that it is easy to determine the size of H and L and they predict timings for this algorithm. The time does not depend on the number of L which happen to be a perfect square. This simplicity means that I can predict optimizations which will make significant difference to the run time for increasing number of digits. The programming skill then is to compute the Cartesian Product of n/2 for L and (n+1)/2 for H integer ranges; then calculate the Inner Product of each with 10**x-10**y for L and 10**x+10**y for H. Efficiently!!! I especially like that this can be described as a problem in Linear Algebra subject to analysis and representation as a graph.--Nigel Galloway (talk) 12:19, 20 December 2019 (UTC)
the 1st REXX version
This is the 1st REXX version, before all the optimizations were added: <lang rexx>/*REXX program to calculate and display an specified amount of rare numbers. */ numeric digits 20; w= digits() + digits() % 3 /*ensure enough decimal digs for calcs.*/ parse arg many start . /*obtain optional argument from the CL.*/ if many== | many=="," then many= 3 /*Not specified? Then use the default.*/
- = 0 /*the number of rare numbers (so far)*/
do n=10 /*N=10, 'cause 1 dig #s are palindromic*/ r= reverse(n) /*obtain the reverse of the number N. */ if r>n then iterate /*Difference will be negative? Skip it*/ if n==r then iterate /*Palindromic? Then it can't be rare.*/ s= n+r /*obtain the sum of N and R. */ d= n-r /* " " difference " " " " */ if iSqrt(s)**2 \== s then iterate /*Not a perfect square? Then skip it. */ if iSqrt(d)**2 \== d then iterate /* " " " " " " " */ #= # + 1 /*bump the counter of rare numbers. */ say right( th(#), length(#) + 9) ' rare number is: ' right( commas(n), w) if #>=many then leave /* [↑] W: the width of # with commas.*/ end /*n*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ th: parse arg th;return th||word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: parse arg x; $= 0; q= 1; do while q<=x; q= q*4
end /*while q<=x*/ do while q>1; q= q % 4; _= x-$-q; $= $ % 2 if _>=0 then do; x= _; $= $ + q end end /*while q>1*/; return $</lang>
Pretty simple, but slow as molasses in January.
Not ready for prime time.
the 2nd REXX version
This is the 2nd REXX version, after all of the hints (properties
of rare numbers) within Shyam Sunder Gupta's
webpage have been incorporated in this REXX program.
<lang rexx>/*REXX program to calculate and display an specified amount of rare numbers. */
numeric digits 20; w= digits() + digits() % 3 /*ensure enough decimal digs for calcs.*/
parse arg many start . /*obtain optional argument from the CL.*/
if many== | many=="," then many= 5 /*Not specified? Then use the default.*/
@dr.=0; @dr.2= 1; @dr.5=1 ; @dr.8= 1; @dr.9= 1 /*rare # must have these digital roots.*/ @ps.=0; @ps.2= 1; @ps.3= 1; @ps.7= 1; @ps.8= 1 /*perfect squares must end in these.*/ @end.=0; @end.1=1; @end.4=1; @end.6=1; @end.9=1 /*rare # must not end in these digits.*/ @dif.=0; @dif.2=1; @dif.3=1; @dif.7=1; @dif.8=1; @dif.9=1 /* A─Q mustn't be these digs.*/ @noq.=0; @noq.0=1; @noq.1=1; @noq.4=1; @noq.5=1; @noq.6=1; @noq.9=1 /*A=8, Q mustn't be*/ @149.=0; @149.1=1; @149.4=1; @149.9=1 /*values for Z that need a even Y. */
- = 0 /*the number of rare numbers (so far)*/
@n05.=0; do i= 1 to 9; if i==0 | i==5 then iterate; @n05.i= 1; end /*¬1 ¬5*/ @eve.=0; do i=-8 by 2 to 8; @eve.i=1; end /*define even " some are negative.*/ @odd.=0; do i=-9 by 2 to 9; @odd.i=1; end /* " odd " " " " */
/*N=10, 'cause 1 dig #s are palindromic*/ do n=10; parse var n a 2 b 3 -2 p +1 q /*get 1st\2nd\penultimate\last digits. */ if @end.q then iterate /*rare numbers can't end in: 1 4 6 or 9*/ if q==3 then iterate
select /*weed some integers based on 1st digit*/ when a==q then do if a==2|a==8 then nop /*if A = Q, then A must be 2 or 8. */ else iterate /*A not two or eight? Then skip.*/ if b\==p then iterate /*B not equal to P? Then skip.*/ end when a==2 then do; if q\==2 then iterate /*A = 2? Then Q must also be 2. */ if b\==p then iterate /*" " " Then B must equal P. */ end when a==4 then do if q\==0 then iterate /*if Q not equal to zero, then skip it.*/ _= b - p /*calculate difference between B and P.*/ if @eve._ then iterate /*Positive not even? Then skip it.*/ end when a==6 then do if @n05.q then iterate /*Q not a zero or five? Then skip it.*/ _= b - p /*calculate difference between B and P.*/ if @eve._ then iterate end when a==8 then do if @noq.q then iterate /*Q isn't one of 2, 3, 7, 8? Skip it.*/ select when q==2 then if b+p\==9 then iterate when q==3 then do; if b>p then if b-p\== 7 then iterate
else if b
1 then if b+p\==11 then iterate
else if b==0 then if b+p\== 1 then iterate
end
when q==8 then if b\==p then iterate
otherwise nop
end /*select*/
end /* [↓] A is an odd digit. */
otherwise n= n + 10**(length(n) - 1) - 1 /*bump N so next N starts with even dig*/
iterate /*Now, go and use the next value of N.*/
end /*select*/
_= a - q; if @dif._ then iterate /*diff of A─Q must be: 0, 1, 4, 5, or 6*/
r= reverse(n) /*obtain the reverse of the number N. */
if r>n then iterate /*Difference will be negative? Skip it*/
if n==r then iterate /*Palindromic? Then it can't be rare.*/
d= n-r; parse var d -2 y +1 z /*obtain the last 2 digs of difference.*/
if @ps.z then iterate /*Not 0, 1, 4, 5, 6, 9? Not perfect sq.*/
select
when z==0 then if y\==0 then iterate /*Does Z = 0? Then Y must be zero. */
when z==5 then if y\==2 then iterate /*Does Z = 5? Then Y must be two. */
when z==6 then if y//2==0 then iterate /*Does Z = 6? Then Y must be odd. */
otherwise if @149.z then if y//2 then iterate /*Z=1,4,9? Y must be even*/
end /*select*/
s= n+r; parse var s -2 y +1 z /*obtain the last two digits of the sum*/
if @ps.z then iterate /*Not 0, 2, 5, 8, or 9? Not perfect sq.*/
select
when z==0 then if y\==0 then iterate /*Does Z = 0? Then Y must be zero. */
when z==5 then if y\==2 then iterate /*Does Z = 5? Then Y must be two. */
when z==6 then if y//2==0 then iterate /*Does Z = 6? Then Y must be odd. */
otherwise if @149.z then if y//2 then iterate /*Z=1,4,9? Y must be even*/
end /*select*/
$= a + b /*a head start on figuring digital root*/
do k=3 for length(n) - 2 /*now, process the rest of the digits. */
$= $ + substr(n, k, 1) /*add the remainder of the digits in N.*/
end /*k*/
/*This REXX pgm uses 20 decimal digits.*/
do while $>9 /* [◄] Algorithm is good for 111 digs.*/
if $>9 then $= left($,1) + substr($,2,1)+ substr($,3,1,0) /*>9? Reduce to a dig*/
end /*while*/
if \@dr.$ then iterate /*Doesn't have good digital root? Skip*/
if iSqrt(s)**2 \== s then iterate /*Not a perfect square? Then skip it. */
if iSqrt(d)**2 \== d then iterate /* " " " " " " " */
#= # + 1 /*bump the counter of rare numbers. */
say right( th(#), length(#) + 9) ' rare number is: ' right( commas(n), w)
if #>=many then leave /* [↑] W: the width of # with commas.*/
end /*n*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
th: parse arg th;return th||word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4))
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: parse arg x; $= 0; q= 1; do while q<=x; q= q*4
end /*while q<=x*/
do while q>1; q= q % 4; _= x-$-q; $= $ % 2
if _>=0 then do; x= _; $= $ + q
end
end /*while q>1*/; return $</lang>
Still pretty sluggish, like molasses in March.
The above REXX program was modified to generate a group of numbers which were AB (two digit) numbers
concatenated with PQ (two digit) numbers to yield a list of four digit numbers.
AB are the 1st two digits of a rare number, and PQ are the last two digits.
This list was sorted and the duplicates removed, and it formed a list of (left 2 digits abutted with the right 2 digits)
numbers that every rare number must have (except for the first rare number (65), which is found the hard
(slow) way.
Tweaks, F#
Kudos to Nigel Galloway for the F# version. I don't know the language well, but was able to cut a few corners to improve performance slightly and add some stats:
- Output at Tio.run (linked):
nth Rare Number elapsed completed 1 65 97 ms 120 ms 2 126 ms 3 127 ms 4 140 ms 5 2 621,770 148 ms 148 ms 6 151 ms 7 253 ms 8 3 281,089,082 261 ms 283 ms 9 4 2,022,652,202 606 ms 5 2,042,832,002 1162 ms 2528 ms 10 3423 ms 11 6 872,546,974,178 16583 ms 7 872,568,754,178 17427 ms 8 868,591,084,757 28471 ms 37612 ms 12
Of course, it can't get too far in the 60 second timeout window. Sometimes it doesn't get past the 5th number, due to poor luck at Tio.run. It can do 13 digits at Tio.run, as long as you start at 13:
nth Rare Number elapsed completed 1 6,979,302,951,885 21129 ms 27470 ms 13
- Output on a i7 core (Visual Studio Console App):
nth Rare Number elapsed completed 1 65 22 ms 24 ms 2 26 ms 3 27 ms 4 28 ms 5 2 621,770 31 ms 31 ms 6 33 ms 7 65 ms 8 3 281,089,082 69 ms 76 ms 9 4 2,022,652,202 221 ms 5 2,042,832,002 373 ms 859 ms 10 1220 ms 11 6 872,546,974,178 6284 ms 7 872,568,754,178 6486 ms 8 868,591,084,757 10336 ms 13739 ms 12 9 6,979,302,951,885 16890 ms 19075 ms 13 10 20,313,693,904,202 105822 ms 11 20,313,839,704,202 106337 ms 12 20,331,657,922,202 116631 ms 13 20,331,875,722,202 118324 ms 14 20,333,875,702,202 122171 ms 15 40,313,893,704,200 257026 ms 16 40,351,893,720,200 258086 ms 283465 ms 14
Checking up to 14 digit numbers in under 5 minutes. Given more time, it can get the correct 17th number (first 15 digit number), but has problems after that. Not sure if it's the memory requirements, or perhaps I pared down Nigel's original program too much for valid output after 14 digits.
I added this here in the discussion and did not post the revised code on the main codepage out of respect for Nigel's original contribution. All I did was tweak it, and did not add any core improvements.
I've been trying to figure out how to put some limits on the permutation of numbers generated, but don't know F# well enough to do it effectively. And when I work in languages I am familiar with, the performance is decades of magnitude worse.--Enter your username (talk) 18:37, 22 September 2019 (UTC)
- As mentioned earlier in this page, I've just added a second Go version based on Nigel's approach which is infinitely faster than the first. You're welcome to try and optimize it further as you're much better at this sort of thing than I am. The perfect square checking might be capable of improvement as I'm just using a simple math.Sqrt approach here rather than having a number of preliminary filters as I did in the first version. --PureFox (talk) 23:11, 24 September 2019 (UTC)
Tweaks, F# (v2)
Thanks again Nigel Galloway, for the improved F# version. (I find it even more delightfully terse, and I understand it even less that the first version.) However, I gave it a couple of shortcuts and got this result on the core i7:
nth Rare Number total time digs (et per dig) 1 65 1 ms 1 ms 2 ( 0 ms) 1 ms 3 ( 0 ms) 2 ms 4 ( 0 ms) 2 ms 5 ( 0 ms) 2 621,770 5 ms 5 ms 6 ( 2 ms) 6 ms 7 ( 0 ms) 29 ms 8 ( 22 ms) 3 281,089,082 31 ms 46 ms 9 ( 16 ms) 4 2,022,652,202 83 ms 5 2,042,832,002 128 ms 461 ms 10 ( 413 ms) 758 ms 11 ( 296 ms) 6 872,546,974,178 1665 ms 7 872,568,754,178 1707 ms 8 868,591,084,757 3203 ms 6932 ms 12 ( 6173 ms) 9 6,979,302,951,885 8657 ms 12306 ms 13 ( 5373 ms) 10 20,313,693,904,202 27181 ms 11 20,313,839,704,202 27278 ms 12 20,331,657,922,202 29120 ms 13 20,331,875,722,202 29399 ms 14 20,333,875,702,202 30104 ms 15 40,313,893,704,200 78829 ms 16 40,351,893,720,200 79112 ms 128604 ms 14 ( 116297 ms) 17 200,142,385,731,002 139117 ms 18 221,462,345,754,122 139142 ms 19 816,984,566,129,618 140051 ms 20 245,518,996,076,442 140431 ms 21 204,238,494,066,002 140679 ms 22 248,359,494,187,442 140687 ms 23 244,062,891,224,042 140778 ms 24 403,058,392,434,500 181008 ms 25 441,054,594,034,340 181033 ms 230265 ms 15 ( 101661 ms) 26 2,133,786,945,766,212 478386 ms 27 2,135,568,943,984,212 499689 ms 28 8,191,154,686,620,818 503747 ms 29 8,191,156,864,620,818 506482 ms 30 2,135,764,587,964,212 507132 ms 31 2,135,786,765,764,212 509065 ms 32 8,191,376,864,400,818 513368 ms 33 2,078,311,262,161,202 532418 ms 34 8,052,956,026,592,517 893558 ms 35 8,052,956,206,592,517 896814 ms 36 8,650,327,689,541,457 962029 ms 37 8,650,349,867,341,457 963704 ms 38 6,157,577,986,646,405 965923 ms 39 4,135,786,945,764,210 1333750 ms 40 6,889,765,708,183,410 2225840 ms 2251017 ms 16 (2020751 ms) 41 86,965,750,494,756,968 2446863 ms 42 22,542,040,692,914,522 2447002 ms 43 67,725,910,561,765,640 3995397 ms 4106524 ms 17 (1855506 ms) 44 284,684,666,566,486,482 7761433 ms 45 225,342,456,863,243,522 7887401 ms 46 225,342,458,663,243,522 7930157 ms 47 225,342,478,643,243,522 8019971 ms 48 284,684,868,364,486,482 8085227 ms 49 871,975,098,681,469,178 8439579 ms 50 865,721,270,017,296,468 9124567 ms 51 297,128,548,234,950,692 9135222 ms 52 297,128,722,852,950,692 9145493 ms 53 811,865,096,390,477,018 9249578 ms 54 297,148,324,656,930,692 9286388 ms 55 297,148,546,434,930,692 9306517 ms 56 898,907,259,301,737,498 9679708 ms 57 631,688,638,047,992,345 16317159 ms 58 619,431,353,040,136,925 16376430 ms 59 619,631,153,042,134,925 16559935 ms 60 633,288,858,025,996,145 16629165 ms 61 633,488,632,647,994,145 16685653 ms 62 653,488,856,225,994,125 18768151 ms 63 497,168,548,234,910,690 24649427 ms 42231937 ms 18 (38125412 ms)
Tested up to 15 digits in under 4 minutes. 16 digits in under 35 minutes, 17 digits under an hour and 10 minutes. It got to the last of the 18 digit rare numbers in under 7 hours, but it takes 11 3/4 hours to complete the block. Still not quite fast enough to go after 19, 20 or 21 digits.
Tio.run (link) version results:
nth Rare Number total time digs (et per dig) 1 65 156 ms 190 ms 2 ( 147 ms) 199 ms 3 ( 0 ms) 200 ms 4 ( 1 ms) 201 ms 5 ( 0 ms) 2 621,770 209 ms 210 ms 6 ( 9 ms) 217 ms 7 ( 6 ms) 326 ms 8 ( 109 ms) 3 281,089,082 335 ms 386 ms 9 ( 59 ms) 4 2,022,652,202 512 ms 5 2,042,832,002 740 ms 1970 ms 10 ( 1583 ms) 3055 ms 11 ( 1085 ms) 6 872,546,974,178 6688 ms 7 872,568,754,178 6938 ms 8 868,591,084,757 13531 ms 28013 ms 12 ( 24957 ms) 9 6,979,302,951,885 34793 ms 48838 ms 13 ( 20825 ms)
One serious shortcut is using [0L;1L;4L;5L;6L] instead of [0..9]. This is allowed because square numbers can't end with 2, 3, 7, or 8, and 9 doesn't count because the numbers being operated upon here have 9 as a factor. --Enter your username (talk) 21:04, 29 September 2019 (UTC)
Tweaks, Go
Thank you PureFox for the Go translation. Here are the results of some code tweaking. Feel free to re-use anything you like on the main page. Some of the corners that were cut: 1. Computed the forward number, the reverse number and the digital root from the "digits" array all at the same time, rather than going back when needed. 2. Used a Boolean array of the last 2 digits of valid squares to determine whether to do the more computationally expensive floating point square root call. 3. The dl array can be seq(-9, 8), rather than seq(-9, 9). It doesn't seem to matter on the low number of digits ( <16 ) we are covering. The digital root fail check can be either before or after the !isSquare() check, you might find it slightly faster one way or the other.
- Output from a core i7:
nth number time completed 1 65 0s 970.4µs 2 970.4µs 3 970.4µs 4 970.4µs 5 2 621,770 970.4µs 970.4µs 6 1.9676ms 7 4.9833ms 8 3 281,089,082 5.9569ms 6.9785ms 9 4 2,022,652,202 19.9197ms 5 2,042,832,002 40.8908ms 84.7729ms 10 137.632ms 11 6 872,546,974,178 646.2443ms 7 872,568,754,178 677.1611ms 8 868,591,084,757 1.0701309s 1.2416797s 12 9 6,979,302,951,885 1.6326327s 1.9797045s 13 10 20,313,693,904,202 10.5358443s 11 20,313,839,704,202 10.6046898s 12 20,331,657,922,202 12.1206037s 13 20,331,875,722,202 12.3569934s 14 20,333,875,702,202 13.0172337s 15 40,313,893,704,200 22.9626308s 16 40,351,893,720,200 23.1066218s 24.4769465s 14 17 200,142,385,731,002 27.4160929s 18 221,462,345,754,122 27.6274982s 19 816,984,566,129,618 30.293394s 20 245,518,996,076,442 31.7365338s 21 204,238,494,066,002 31.9389919s 22 248,359,494,187,442 32.0028151s 23 244,062,891,224,042 32.3977374s 24 403,058,392,434,500 36.6045135s 25 441,054,594,034,340 36.8109598s 38.1518922s 15
It can't get past 15 digits, due to the memory requirement. I purposely let the "natural" order of the results display, as I was more interested in the performance time of each result.
- Output from Tio.run (linked):
nth number time completed 1 65 104.828µs 131.427µs 2 139.331µs 3 178.561µs 4 200.489µs 5 2 621,770 698.249µs 757.813µs 6 1.42756ms 7 8.927975ms 8 3 281,089,082 10.244811ms 12.738426ms 9 4 2,022,652,202 72.43969ms 5 2,042,832,002 123.310535ms 218.093377ms 10 415.295536ms 11 6 872,546,974,178 1.93598265s 7 872,568,754,178 2.000165728s 8 868,591,084,757 2.821645253s 3.286164167s 12 9 6,979,302,951,885 5.924838452s 6.864383645s 13
It can't get past 13 digits on Tio.run, due to memory requirement. Execution time at Tio.run is often worse than this, but it always completes in the 60 second time limit. --Enter your username (talk) 22:30, 28 September 2019 (UTC)
- Thanks for trying to do something here.
- Curiously, it's slower than before when I run it several times on my core i7. The range to get to 15 digits is between 46 and 49 seconds whereas the previous version is steady at around 42 seconds. I've recently upgraded from Go version 1.12.9 to 1.13.1 (the latest as I post this) but I doubt whether it would affect this particular program.
- As you're getting 38 seconds for your 'tweaked' version, then your core i7 is probably faster than mine though presumably that time was faster than the original version on the same machine so I'm not sure what to make of it.
- As you say there are memory problems when trying to go above 15 digits, though I see that Nigel has today posted a new F# version which has managed to reach 17 digits without using Cartesian products. So I think we're going to have to take another look at it anyway. --PureFox (talk) 18:41, 29 September 2019 (UTC)
- The original version of your 2nd Go program runs about 2-3 seconds slower than the version I put at the Tio.run link. So these tweaks are not much of an improvement. Thanks so much for sharing your version. Not sure why it would go slower on your core i7. I just installed Go for the first time at v 1.13.1. I am careful to keep any other programs from executing concurrently that might interfere with the timing measurements. The full name of my cpu is i7-7700 @ 3.6Ghz. Operating on Win10. It is not overclocked, I have not verified it's speed with any benchmarking software. --Enter your username (talk) 04:34, 30 September 2019 (UTC)
- Mine's an Intel 8565U which has a much lower base frequency (1.8 GHz) but a higher turbo frequency (4.6 GHz) than yours (4.2 GHz I believe). I suspect yours will be faster overall but there's probably not a great deal in it.
- Incidentally, I'm using Ubuntu 18.04 rather than Windows 10 but I've no reason to suppose that Go executes faster on one rather than the other nowadays.
- Anyway, the good news is that I've come up with a new strategy which is significantly faster - 15 digits is processed in around 28 seconds compared to 42 seconds previously.
- Basically, I'm using a combination of Nigel and Shyam's approachs which cuts down the Cartesian products quite a lot but, unfortunately, still not enough to process 16 digits before running out of memory.
- To deal with the memory problem, I've added a second version which delivers the Cartesian products 100 at a time rather than en masse. Not surprisingly, the former is slower than the latter and it's back up to about 43 seconds to get to 15 digits. However, 16 digits takes less than 7 minutes and 17 digits less than 12 minutes - I couldn't be bothered to go any further than that - so it's a worthwhile trade-off.
- The idiomatic way to 'yield' values in Go is to spawn a goroutine and pass it a channel (or a buffered channel in this case). However, I'd stress here that I'm not trying to parallelize the algorithm (although one certainly could) as I don't like doing this for RC tasks. --PureFox (talk) 15:14, 30 September 2019 (UTC)
- I thought I'd see if I could extend the program to process 18 digit numbers but was surprised when it blew up with an OOM error after hitting the 56th rare number! Frankly, I don't understand why - there appeared to be plenty of unused memory when I profiled it. It may be due to heap fragmentation as the Go GC doesn't compact the heap after a collection and so needs to find a large enough slot for new allocations.
- Anyway, I thought I'd get rid of the Cartesian product function altogether and replace it with (in effect) a nested loop and was glad I did as this has restored performance to previous levels and solved the OOM problem. 15, 16 and 17 digits are dispatched in 28 seconds, 4 minutes and 6 minutes respectively and even 18 digits completes in a tolerable 74 minutes.
- To reliably go any further than this would require the use of big integers (unpleasant and relatively slow in Go) as signed 64 bit integers have a 19 digit maximum. It might be possible to use unsigned 64 bit integers (20 digit maximum) though this would require some fancy footwork to deal with negative numbers and subtraction. So I think that's my lot now :) --PureFox (talk) 20:04, 2 October 2019 (UTC)
21+ digit rare numbers
Well, one anyway (so far). I tweaked the BigInteger version of the C# program to skip to start at 21 digits. Around 6 hours, I got the first one: 219,518,549,668,074,815,912, with the sum = 20,953,210,2682, and the difference = 8,877,0002. Still have no idea how long it will take to finish the block of 21 digit numbers. Since the difference found so far was a relatively low number, it probably has quite a while to go.
I am also running another instance that checks the block of 20 digit numbers (in order to verify the algorithm against the table of known rare numbers), but after 6 hours, it still hasn't come up with anything yet. A little surprising, as there are a few 20 digit rare numbers with 7 digit differences. If I don't see anything on the 20 digit run in 6 more hours, there may be some kind of issue to work out. --Enter your username (talk) 02:52, 21 October 2019 (UTC)
P.S. 5 found so far:
Nth Time (hours) rare number 85 6 219,518,549,668,074,815,912 86 10 1/2 837,982,875,780,054,779,738 87 11 1/2 208,393,425,242,000,083,802 88 12 1/3 286,694,688,797,362,186,682 89 13 2/3 257,661,195,832,219,326,752
--Enter your username (talk) 21:29, 22 October 2019 (UTC)
- In the Go program, I took advantage of Shyam's observation that no rare number up to 10^20 ended in 3. So, as far as the 21 digit numbers are concerned, a possible fly in the ointment is that they could in theory end in 3 (with a first digit of 8) which would, of course, mean adding another key/value pair to the 'fml' dictionary with other consequent amendments. The chances are that there won't be any such numbers but you might want to bear it in mind if you have occasion to run this instance again.
- As far as the 20 digit numbers are concerned, there shouldn't be any issues if you're running a BigInteger version for that too and adjusting the IsSquare method accordingly.
--PureFox (talk) 12:58, 23 October 2019 (UTC)
- Regarding missing solutions at 20 digits, I found that the Math.Sqrt() function may drop a few bits of resolution at 20 digits or more. Not totally unexpected. However, the Math.Sqrt() function can be used as an initial accurate first guess in a Newton's method integer square root function.
- There is an integer square root function that only uses integers and floating point multiple and division isn't used. -- Gerard Schildberger (talk) 07:31, 12 January 2020 (UTC)
- I agree the 8,3 combo should be added for 21+ digits computation. For the task as defined, (5th to 8th number), it's not needed. But for going beyond the table on Shyam Sunder Gupta's webpage, one really needs to consider that combination.
- I e-mailed Shyam Sunder Gupta and he said he'd update his webpage. He said that he figured nobody would compute rare numbers that high, so he didn't bother to enter the updated list before. He also mentioned that he had found a rare number ending in the decimal digit 3. -- Gerard Schildberger (talk) 07:26, 12 January 2020 (UTC)
- I see this BigInteger conversion attempt as a means of reaching a few 21 digit numbers (which it did) and a means to reveal any shortcomings in the existing ulong algorithm which don't translate well to the BigInteger version (which it also did, I guess). If only it wasn't so impractically slow. If I could get it an order of magnitude faster, it would easier to persue this further. Creating a multi-tasking version would probably only go 2 to 4 times faster.--Enter your username (talk) 06:57, 24 October 2019 (UTC)
There only seem to be 5 21 digit rare numbers, so I started looking at 22 digits. I found that each odd number of digits takes less time (about 80% of the time) of the previous even number of digits, but each even/odd pair (number of digits such as 16/17 vs 14/15) takes about 20 times a long as the previous pair, so the computation time increases dramatically for results above 19 digits. Here are number of digits 21 and 22:
S.No. R R+R1 R-R1 85 208393425242000083802 204150294022 1158663002 86 219518549668074815912 209532102682 88770002 87 257661195832219326752 226998922482 1930896002 88 286694688797362186682 239452699422 1158663002 89 837982875780054779738 409384944262 736593002 90 2414924301133245383042 694172869282 33299966702 91 2414924323311045383042 694172869282 33300033302 92 2414946523311023183042 694172869282 33366633302 93 2576494891793995836752 717835697482 3299967002 94 2576494893971995836752 17835697482 3300033002 95 2620937863931054483162 723517958682 26633367302 96 2620955623931476283162 723517958682 26699967302 97 2620955641393276283162 723517958682 26700032702 98 2622935621573476481162 723517958682 33299966702 99 2622935643751276481162 723517958682 33300033302 100 2622937641933274481162 723517958682 33306033302 101 2622955841933256281162 723517958682 33360633302 102 2622957843751254281162 723517958682 33366633302 103 2727651947516658327272 738572306122 6429474002 104 2747736918335953517072 738572306122 63705041402 105 2788047668617596408872 746732524122 266730002 106 2788047848617776408872 746732524122 327330002 107 2788047868437576408872 746732524122 333330002 108 2788047888617376408872 746732524122 339330002 109 2939501759705522349392 766742069722 2636373002 110 2939503375709360349392 766742069722 2696973002 111 2939503537707740349392 766742069722 2702973002 112 2939521359525562149392 766742069722 3297033002 113 2939521557527542149392 766742069722 3303033002 114 2939523577527340149392 766742069722 3363633002 115 2939523779525320149392 766742069722 3369633002 116 2959503377707360349192 766742069722 63303033602 117 6344828989519887483525 1076971535312 330300030332 118 8045841652464561594308 1268100678462 32999996702 119 8045841654642561594308 1268100678462 33000003302 120 8655059576513659814468 1315266100062 32969703302 121 8655059772157639814468 1315266100062 32970296702 122 8655079374155679614468 1315266100062 33029696702 123 8655079574515659614468 1315266100062 33030303302
That took about 5 3/4 days of computation. Only one odd number. Lots of 2,2 combinations there. Nearly half of all rare numbers under 21 digits start and end with 2. The trend continues above 20 digits with over half starting and ending with 2. --Enter your username (talk) 06:17, 2 December 2019 (UTC)
- Oops, it appears that I missed one, Shyam Sunder Gupta has published an updated list of 124 Rare numbers up to 22 digits on his webpage, back on December 15th. The one I missed is the first Rare number ending with 3.
124 8888070771864228883913 1099179648492 754598074952
- At least that verifies that there are only 5 21 digit Rare numbers. --Enter your username (talk) 22:46, 26 December 2019 (UTC)
Some 23s:
125 (20,006,212,343,920,163,220,002) 126 (20,404,210,361,902,143,200,402) 127 (21,544,373,975,964,337,344,512) 128 (22,781,275,420,027,357,218,722) 129 (80,618,209,916,486,890,281,608) 130 (81,313,065,142,333,312,588,218) 131 (84,247,683,299,691,574,674,248) 132 (89,650,295,750,128,200,205,698)
That's 8 found for 23 digits, taking ~4 1/5 days to go through the combinations. --Enter your username (talk) 17:54, 15 December 2019 (UTC)
- Now that you've established that there are five 21 digit rare numbers, it might be worth mailing SSG (at guptass@rediffmail.com) to see if he'll add them to his list.
- It's a pity that we don't have 128 bit integers to speed up the calculations. There's a proposal to add them to Go which has plenty of support but the Go team doesn't seem particularly keen.
- C# does of course have its 'decimal' type which is 16 bit and can deal with up to 28 digit integers. Although it's much slower than 'double', it might still be faster than BigInteger.
- I also found this open source library for C# which might be worth checking out. --PureFox (talk) 17:25, 2 December 2019 (UTC)
- To get to 22 digits, I had to use multitasking and that C# UI128 package you spotted. The performance of the UI128 package is good, only about two and a half times worse than UI64's, whereas BigInteger is around 7 to 8 times worse. The UI128 package should go up to 38 decimal digits or so. But because it takes 20 times longer for each additional pair of digits, I don't think 38 digits a possibilty with the current algorithm. I am contemplating a new algorithm that could be more efficient.
- Regarding the 5 21 digit rare numbers found, to prove that there are only 5, what is really needed is to prove that all 1021 - 5 of the possible 1021 are not rare. If the algorithm that finds 5 misses a couple, thats not a good result. I'm confident to report 5 found, but not quite absolutely sure they are the only 5 at this point in time.--Enter your username (talk) 03:04, 3 December 2019 (UTC)
- I've entered code in C++ which I expect using clang++ on the monster beasts you have for computers will complete 21 in a day and a quarter and 22 in less than 4 days. The difference between clang++ and g++ is suprising. It would be interesting to know how MSVC does.--Nigel Galloway (talk) 12:28, 20 December 2019 (UTC)
- I don't have clang but, compiling your C++ code for 10 to 19 digits on my core i7 using g++ v7.4 (-std=c++17 -O3) on Ubuntu 18.04, produces execution times of 11.7, 78, 221 and 1484 seconds for rare numbers with 16, 17, 18 and 19 digits respectively. The corresponding times for the Go entry (with the Julia entry not far behind) were 221, 355, 4532 and 6610 seconds so, even if we assume these languages are 2 or 3 times slower than C++, the algorithm you're now using is considerably more efficient than what we had before.
- Thanks for that. I've timed it on a Core I5 1035G1 and obtained 17->33sec; 18->92sec; and 19->741sec. For comparison I compiled the C# and obtained 17->6m45sec (compared to 2m12sec on an i7 7700 claimed on the page).--Nigel Galloway (talk) 16:40, 13 March 2020 (UTC)
- We've certainly had a wide variation in the timings for this task and it appears now that g++ is much slower than both clang and mingw for some reason. The C# time for 17 numbers looks right to me as my Go translation was only a second or two behind, again using Core I7. I'm surprised how much quicker C++ is than C#, its stable-mate VB.NET and Go for this task. Although Enter your Username has clearly tried hard to minimize the effect of GC by declaring huge swathes of variables 'static', the performance gap is still huge. --PureFox (talk) 11:35, 14 March 2020 (UTC)
- I thought for good measure I'd add a Go translation of your C++ program (10 to 19 digits version) and this has cut the execution time from 54 to 21 minutes in round figures which seems more in line with expectations. For comparison, I compiled the C++ program again (using g++ 7.5.0 this time) and ran it on the same machine but the total execution time was almost identical at around 30 minutes so it's difficult to know what to make of it. Perhaps g++ is not yet quite up to speed with C++ 17 features? --PureFox (talk) 17:07, 16 March 2020 (UTC)
- I thought for good measure I'd (tit for tat?) install Go and run your goTurbo code on my i5-1035G1. I obtained the following:
40 8,650,349,867,341,457 16: 00:00:06.403 00:00:09.163 43 86,965,750,494,756,968 17: 00:00:42.818 00:00:51.982 (mingw real 0m33.328s) 63 898,907,259,301,737,498 18: 00:02:01.282 00:02:53.264 (mingw real 1m32.945s) 75 8,320,411,466,598,809,138 19: 00:15:36.454 00:18:29.719 (mingw real 12m21.298s)
I think this demonstrates that the task should require at least the first 63 Rare numbers!!! --Nigel Galloway (talk) 12:22, 19 March 2020 (UTC)
- LOL, the Go version is even faster on your i5 than it is on my i7, and only about 50% behind mingw! I imagine you're running it on Windows 10 whereas I'm using Ubuntu 18.04 but that shouldn't make much difference. Probably should have bought an i7 with a higher basic clock speed as performance can be a bit disappointing at times.
- I find it hard to believe that clang++ could be 3 times faster than g++ (though you can get some strange results with these CPU-intensive tasks) and, although I no longer have an up to date Windows machine, on past form I'd be surprised if Visual C++ were any faster than g++ itself. Enter your username may be able to confirm the position there. --PureFox (talk) 20:53, 20 December 2019 (UTC)
- I tried compiling it using MSVC. It crashed the compiler, well at least caused it to catch an internal error.--Nigel Galloway (talk) 16:40, 13 March 2020 (UTC)