prog

frontpage - thread list - new thread - preferences - ?

What are you working on?

168 2020-12-31 15:16

To divide an u32 by 3:

base 2 div 3 limit 4,294,967,295
try 1 shift 2 exp 4
  factor 2 over 2 product 8,589,934,590
try 2 shift 3 exp 8
  factor 3 over 1 product 4,294,967,295
try 3 shift 4 exp 16
  factor 6 over 2 product 8,589,934,590
try 4 shift 5 exp 32
  factor 11 over 1 product 4,294,967,295
try 5 shift 6 exp 64
  factor 22 over 2 product 8,589,934,590
try 6 shift 7 exp 128
  factor 43 over 1 product 4,294,967,295
try 7 shift 8 exp 256
  factor 86 over 2 product 8,589,934,590
try 8 shift 9 exp 512
  factor 171 over 1 product 4,294,967,295
try 9 shift 10 exp 1,024
  factor 342 over 2 product 8,589,934,590
try 10 shift 11 exp 2,048
  factor 683 over 1 product 4,294,967,295
try 11 shift 12 exp 4,096
  factor 1,366 over 2 product 8,589,934,590
try 12 shift 13 exp 8,192
  factor 2,731 over 1 product 4,294,967,295
try 13 shift 14 exp 16,384
  factor 5,462 over 2 product 8,589,934,590
try 14 shift 15 exp 32,768
  factor 10,923 over 1 product 4,294,967,295
try 15 shift 16 exp 65,536
  factor 21,846 over 2 product 8,589,934,590
try 16 shift 17 exp 131,072
  factor 43,691 over 1 product 4,294,967,295
try 17 shift 18 exp 262,144
  factor 87,382 over 2 product 8,589,934,590
try 18 shift 19 exp 524,288
  factor 174,763 over 1 product 4,294,967,295
try 19 shift 20 exp 1,048,576
  factor 349,526 over 2 product 8,589,934,590
try 20 shift 21 exp 2,097,152
  factor 699,051 over 1 product 4,294,967,295
try 21 shift 22 exp 4,194,304
  factor 1,398,102 over 2 product 8,589,934,590
try 22 shift 23 exp 8,388,608
  factor 2,796,203 over 1 product 4,294,967,295
try 23 shift 24 exp 16,777,216
  factor 5,592,406 over 2 product 8,589,934,590
try 24 shift 25 exp 33,554,432
  factor 11,184,811 over 1 product 4,294,967,295
try 25 shift 26 exp 67,108,864
  factor 22,369,622 over 2 product 8,589,934,590
try 26 shift 27 exp 134,217,728
  factor 44,739,243 over 1 product 4,294,967,295
try 27 shift 28 exp 268,435,456
  factor 89,478,486 over 2 product 8,589,934,590
try 28 shift 29 exp 536,870,912
  factor 178,956,971 over 1 product 4,294,967,295
try 29 shift 30 exp 1,073,741,824
  factor 357,913,942 over 2 product 8,589,934,590
try 30 shift 31 exp 2,147,483,648
  factor 715,827,883 over 1 product 4,294,967,295
try 31 shift 32 exp 4,294,967,296
  factor 1,431,655,766 over 2 product 8,589,934,590
try 32 shift 33 exp 8,589,934,592
  factor 2,863,311,531 over 1 product 4,294,967,295
x div 3 -> (x * 2,863,311,531) >>(2) 33
  basebits 64 max 12,297,829,381,041,378,645

the magic factor is:

>>> hex (2863311531)
'0xaaaaaaab'

Examples:

>>> (123456789 * 2863311531) >> 33
41152263
>>> 123456789 // 3
41152263
>>> (20202020 * 2863311531) >> 33
6734006
>>> 20202020 // 3
6734006
>>> (13371337 * 2863311531) >> 33
4457112
>>> 13371337 // 3
4457112

199