prog

frontpage - thread list - new thread - preferences - ?

What are you working on?

167 2020-12-31 15:14

For an u32:

base 2 div 10 limit 4,294,967,295
try 1 shift 4 exp 16
  factor 2 over 4 product 17,179,869,180
try 2 shift 5 exp 32
  factor 4 over 8 product 34,359,738,360
try 3 shift 6 exp 64
  factor 7 over 6 product 25,769,803,770
try 4 shift 7 exp 128
  factor 13 over 2 product 8,589,934,590
try 5 shift 8 exp 256
  factor 26 over 4 product 17,179,869,180
try 6 shift 9 exp 512
  factor 52 over 8 product 34,359,738,360
try 7 shift 10 exp 1,024
  factor 103 over 6 product 25,769,803,770
try 8 shift 11 exp 2,048
  factor 205 over 2 product 8,589,934,590
try 9 shift 12 exp 4,096
  factor 410 over 4 product 17,179,869,180
try 10 shift 13 exp 8,192
  factor 820 over 8 product 34,359,738,360
try 11 shift 14 exp 16,384
  factor 1,639 over 6 product 25,769,803,770
try 12 shift 15 exp 32,768
  factor 3,277 over 2 product 8,589,934,590
try 13 shift 16 exp 65,536
  factor 6,554 over 4 product 17,179,869,180
try 14 shift 17 exp 131,072
  factor 13,108 over 8 product 34,359,738,360
try 15 shift 18 exp 262,144
  factor 26,215 over 6 product 25,769,803,770
try 16 shift 19 exp 524,288
  factor 52,429 over 2 product 8,589,934,590
try 17 shift 20 exp 1,048,576
  factor 104,858 over 4 product 17,179,869,180
try 18 shift 21 exp 2,097,152
  factor 209,716 over 8 product 34,359,738,360
try 19 shift 22 exp 4,194,304
  factor 419,431 over 6 product 25,769,803,770
try 20 shift 23 exp 8,388,608
  factor 838,861 over 2 product 8,589,934,590
try 21 shift 24 exp 16,777,216
  factor 1,677,722 over 4 product 17,179,869,180
try 22 shift 25 exp 33,554,432
  factor 3,355,444 over 8 product 34,359,738,360
try 23 shift 26 exp 67,108,864
  factor 6,710,887 over 6 product 25,769,803,770
try 24 shift 27 exp 134,217,728
  factor 13,421,773 over 2 product 8,589,934,590
try 25 shift 28 exp 268,435,456
  factor 26,843,546 over 4 product 17,179,869,180
try 26 shift 29 exp 536,870,912
  factor 53,687,092 over 8 product 34,359,738,360
try 27 shift 30 exp 1,073,741,824
  factor 107,374,183 over 6 product 25,769,803,770
try 28 shift 31 exp 2,147,483,648
  factor 214,748,365 over 2 product 8,589,934,590
try 29 shift 32 exp 4,294,967,296
  factor 429,496,730 over 4 product 17,179,869,180
try 30 shift 33 exp 8,589,934,592
  factor 858,993,460 over 8 product 34,359,738,360
try 31 shift 34 exp 17,179,869,184
  factor 1,717,986,919 over 6 product 25,769,803,770
try 32 shift 35 exp 34,359,738,368
  factor 3,435,973,837 over 2 product 8,589,934,590
x div 10 -> (x * 3,435,973,837) >>(2) 35
  basebits 64 max 14,757,395,256,390,660,915

we can multiply by 3,435,973,837 then right shift by 35, and we need 64 bits for the multiplication. Examples:

>>> (123456789 * 3435973837) >> 35
12345678
>>> (20202020 * 3435973837) >> 35
2020202
>>> (13371337 * 3435973837) >> 35
1337133

199