prog

frontpage - thread list - new thread - preferences - ?

What are you working on?

169 2020-12-31 15:18

If we have a ternary machine and we want to produce hex strings of numbers up to a million:

base 3 div 16 limit 1,000,000
try 1 shift 3 exp 27
  factor 2 over 5 product 5,000,000
try 2 shift 4 exp 81
  factor 6 over 15 product 15,000,000
try 3 shift 5 exp 243
  factor 16 over 13 product 13,000,000
try 4 shift 6 exp 729
  factor 46 over 7 product 7,000,000
try 5 shift 7 exp 2,187
  factor 137 over 5 product 5,000,000
try 6 shift 8 exp 6,561
  factor 411 over 15 product 15,000,000
try 7 shift 9 exp 19,683
  factor 1,231 over 13 product 13,000,000
try 8 shift 10 exp 59,049
  factor 3,691 over 7 product 7,000,000
try 9 shift 11 exp 177,147
  factor 11,072 over 5 product 5,000,000
try 10 shift 12 exp 531,441
  factor 33,216 over 15 product 15,000,000
try 11 shift 13 exp 1,594,323
  factor 99,646 over 13 product 13,000,000
try 12 shift 14 exp 4,782,969
  factor 298,936 over 7 product 7,000,000
try 13 shift 15 exp 14,348,907
  factor 896,807 over 5 product 5,000,000
x div 16 -> (x * 896,807) >>(3) 15
  basebits 26 max 896,807,000,000

we can multiply by 896,807 then right shift by 15 ternary positions. The multiplication requires 26 ternary positions. Examples:

>>> (123456 * 896807) // (3 ** 15)
7716
>>> 123456 // 16
7716
>>> (202020 * 896807) // (3 ** 15)
12626
>>> 202020 // 16
12626
>>> (133713 * 896807) // (3 ** 15)
8357
>>> 133713 // 16
8357

If we meet a time traveler from ancient Sumer who has a base-60 machine, and we want to produce hex strings of numbers up to a million:

base 60 div 16 limit 1,000,000
try 1 shift 1 exp 60
  factor 4 over 4 product 4,000,000
try 2 shift 2 exp 3,600
  factor 225 over 0 product 0
x div 16 -> (x * 225) >>(60) 2
  basebits 5 max 225,000,000

The final 'over' being 0 shows that this will work for arbitrarily large numbers, provided that we have the space for the multiplication. Examples:

>>> (123456 * 225) // (60 ** 2)
7716
>>> 123456 // 16
7716
>>> (202020 * 225) // (60 ** 2)
12626
>>> 202020 // 16
12626
>>> (133713 * 225) // (60 ** 2)
8357
>>> 133713 // 16
8357

The advantage of this iterative method is that it allows the problem to be tackled using only basic knowledge of fractions, without having to resort to rings and modular inverses. Here is a small challenge. Try to find a necessary and sufficient condition for the base and the divisor so that the final 'over' value will be 0. Once you have the condition try to write some code that implements it with some reasonable efficiency.

199