Anonymous user
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 17:44, 16 July 2019
, 4 years ago→any ideas of optimizations ?: speed up adding to base x <127
m (→Finding maximal distances to check if number needs extra digit: how to find the values with formula) |
m (→any ideas of optimizations ?: speed up adding to base x <127) |
||
Line 70:
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%
==Space compression and proof ?==
| |||