Talk:First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
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: | Line 70: | ||
26.508s</pre> |
26.508s</pre> |
||
It takes 583.903.946 long and short additions |
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 ?== |
==Space compression and proof ?== |