Talk:First perfect square in base n with n unique digits: Difference between revisions
Talk:First perfect square in base n with n unique digits (view source)
Revision as of 13:35, 7 November 2020
, 3 years agoThundergnat moved page Talk:First perfect square in base N with N unique digits to Talk:First perfect square in base n with n unique digits: Follow normal task title capitalization policy
m (→Finding maximal distances to check if number needs extra digit: how to find the values with formula) |
Thundergnat (talk | contribs) m (Thundergnat moved page Talk:First perfect square in base N with N unique digits to Talk:First perfect square in base n with n unique digits: Follow normal task title capitalization policy) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
==Incorrect Example==
Base 3 : Num 11 sqr 121
--LambertDW 18:28, 2 March 2020 (UTC)
Hmm. I am the original task author, but that list was added by someone else well after the task was written. You are correct though, that is wrong. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 23:19, 2 March 2020 (UTC)
==Leading zeros ?==
Line 70 ⟶ 76:
26.508s</pre>
It takes 583.903.946 long and short additions
: speed up adding in base < 127 < 256 Div 2 by using Uin64 to pack 8 digits.By offsetting every digit of the sum by 256-base=$FF-base one gets an natural carry into the next digit.
:example: base = 10 89 -> $0809 offset every digit by $F6 ( the new $00 ) -> $FEFF and add 1 = $0002
<pre>
$FEFF
+$0002
$FF01 </pre>
:Now check which digit overflows.If one digit overflows, its highest bit is not set anymore, so the digit 0 aka $F6 must be added
<pre>
$FF01 ( pre-result )
XOR $8080 (= Overflow-MASK )
= $0080 ( now shr by 7 Bits )
= $0001 ( Multiply by $F6 -> zero Offset )
* $F6 ( = zero offset mask )
= $00F6
+ $FF01 (now ADD pre-result )
= $FFF7 ( if one like convert back subtract "zero"
- $F6F6
= $0901 -> 91</pre>
: it speeds up additions by a factor of 3, but checking the used digits takes ~ 40% of runtime - 60%/3+40% = 60%
:: think of base 10 and the square of the last 2-digits. of a number.If the last 2 digits of the square are the same you need not to test the complete number.
<pre> 0 10 12 20 30 38 40 50 60 62 70 80 88 90
86 of 100 are left over not that impressive</pre>
::using more digits increases the proportion even more 4 digits -> 4660 of 10000 are left over to test.
::but 4 digits to base 37 lead to 1542240 of 1874161 need to be checked.Not that useful.
==Space compression and proof ?==
| |||