Rosetta Code

Palindromic gapful numbers: Difference between revisions

Page Discussion

Palindromic gapful numbers (view source)

Revision as of 16:48, 18 March 2022

746 bytes added ,  2 years ago
m
→‎Ludicrously fast to 10,000,000,000,000,000,000th: added online link
Line 3,074:
 
=== Ludicrously fast to 10,000,000,000,000,000,000th ===
You can run this online [http://phix.x10.mx/p2js/pgn.htm here].
Astonishingly this is all done with standard precision numbers, &lt; 2<sup><small>53</small></sup>. You realise this is like ten thousand times the ''square'' of the previous limits, and still far faster.<br>
I will credit [[Self_numbers#AppleScript]] and the comment by Nigel Galloway on the talk page for ideas that inspired me.
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Palindromic_gapful_numbers.exw
-- demo\rosetta\Palindromic_gapful_numbers.exw
-- ===========================================
--
-- Astonishingly this is all done with standard precision numbers, &lt;2^53.
-- I will credit https://rosettacode.org/wiki/[[Self_numbers#AppleScript]] and comment by Nigel Galloway
-- the comment by Nigel Galloway on the talk page for ideas that inspired me.
--
-- A palindrome such as 9459549 can be constructed/broken down into
Line 3,133 ⟶ 3,134:
-- will probably be skipped.
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)}),</span><span style="color: #000000;">9</span><span style="color: #0000FF;">))</span>
<span style="color: #000080;font-style:italic;">-- ie <nowiki>{{</nowiki>{1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>2}, {2}, {2}, {2}, {2}, {2}, {2}, {2}, {2<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>3}, {3}, {3}, {3}, {3}, {3}, {3}, {3}, {3<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>4}, {4}, {4}, {4}, {4}, {4}, {4}, {4}, {4<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>5}, {5}, {5}, {5}, {5}, {5}, {5}, {5}, {5<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>6}, {6}, {6}, {6}, {6}, {6}, {6}, {6}, {6<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>7}, {7}, {7}, {7}, {7}, {7}, {7}, {7}, {7<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>8}, {8}, {8}, {8}, {8}, {8}, {8}, {8}, {8<nowiki>}}</nowiki>,
-- <nowiki>{{</nowiki>9}, {9}, {9}, {9}, {9}, {9}, {9}, {9}, {9<nowiki>}}</nowiki>}
-- aka 1 rem 11 .. 1 rem 99 are all 1,
-- .. 9 rem 11 .. 9 rem 99 are all 9.
Line 3,153 ⟶ 3,155:
-- it will be at most (on 64-bit) 9 * 9 * 42.)
--</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rmdrrmdrn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- digit is the outer 0..9 (obvs 0 always yields 0),
Line 3,159 ⟶ 3,161:
-- pow is trailing zeros (0,1,2,.. for eg 101,1010,10100),
-- n is 1..9 for 11..99
-- eg rmdrrmdrn(4,3,2,1) yields remainder(4000400,11), but
-- that === remainder(remainder(4000000,11)+
-- remainder( 400,11),11), and
-- if k = remainder(4*10^(m-1),11) [already known] then
-- remainder(4*10^m,11) === remainder(k*10,11), so
Line 3,169 ⟶ 3,171:
<span style="color: #008080;">if</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">g</span>
<span style="color: #008080004080;">whilesequence</span> <span style="color: #7060A8000000;">lengthcdn</span> <span style="color: #0000FF;">(=</span> <span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">+</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000008080;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&=while</span> <span style="color: #7060A8;">remainderlength</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cachecdn</span><span style="color: #0000FF;">[)<</span><span style="color: #000000;">digitgap</span><span style="color: #0000FF;">][+</span><span style="color: #000000;">npow</span><span style="color: #0000FF;">][$]*+</span><span style="color: #000000;">102</span><span style="color: #0000FF;">,</span><span style="color: #000000008080;">nn</span><span style="color: #0000FF;">)do</span>
<span style="color: #000000;">palscache</span> <span style="color: #0000FF;">=[</span> <span style="color: #7060A8000000;">appenddigit</span><span style="color: #0000FF;">(][</span><span style="color: #000000;">palsn</span><span style="color: #0000FF;">,]</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000000080;">l</span><span font-style="color: #0000FFitalic;">)&</span><span-- style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><spankill style="color: #000000;">lhs</span><span style="color: #0000FF;">)refcount)</span>▼
<span style="color: #000000;">cdn</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cdn</span><span style="color: #0000FF;">[$]*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cdn</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">0</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">cachecdn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">+</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">cachecdn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 3,184 ⟶ 3,189:
-- palcount, to_skip, count: self explanatory (aka got/ignore/target)
-- l: length of inner to be filled in
-- r: remainder of outer, eg remainder(9400049,11), built from rmdrrmdrn()
-- p: left shift (should in fact always equal length(lhs), I think)
-- dd: outermost 1..9 (despite the name, it's a single digit)
Line 3,196 ⟶ 3,201:
<span style="color: #000000;">skip</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rmdrrmdrn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">),</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r2</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
Line 3,203 ⟶ 3,208:
<span style="color: #000000;">skip</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000080;font-style:italic;">-- pals = append(pals,lhs&repeat(d+'0',l)&reverse(lhs))
▲ <span style="color: #000000;">pals</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">))</span>
-- pals = append(deep_copy(pals),deep_copy(lhs)&repeat(d+'0',l)&reverse(lhs))</span>
<span style="color: #000000;">pals</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">),</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 3,223 ⟶ 3,230:
<span style="color: #004080;">string</span> <span style="color: #000000;">lhs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">&(</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ie "1" or "2" .. or "9"</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">palcount</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">count</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rmdrrmdrn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">,</span><span style="color: #000000;">palcount</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">palindromicgapfuls</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">palcount</span><span style="color: #0000FF;">,</span><span style="color: #000000;">to_skip</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
Petelomax
7,830

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/295872"