prog

frontpage - thread list - new thread - preferences - ?

What are you working on?

166 2020-12-31 15:12

This is an inner working function called by a wrapper that takes care of invalid arguments. An example that divides an u16 by 10:

base 2 div 10 limit 65,535
try 1 shift 4 exp 16
  factor 2 over 4 product 262,140
try 2 shift 5 exp 32
  factor 4 over 8 product 524,280
try 3 shift 6 exp 64
  factor 7 over 6 product 393,210
try 4 shift 7 exp 128
  factor 13 over 2 product 131,070
try 5 shift 8 exp 256
  factor 26 over 4 product 262,140
try 6 shift 9 exp 512
  factor 52 over 8 product 524,280
try 7 shift 10 exp 1,024
  factor 103 over 6 product 393,210
try 8 shift 11 exp 2,048
  factor 205 over 2 product 131,070
try 9 shift 12 exp 4,096
  factor 410 over 4 product 262,140
try 10 shift 13 exp 8,192
  factor 820 over 8 product 524,280
try 11 shift 14 exp 16,384
  factor 1,639 over 6 product 393,210
try 12 shift 15 exp 32,768
  factor 3,277 over 2 product 131,070
try 13 shift 16 exp 65,536
  factor 6,554 over 4 product 262,140
try 14 shift 17 exp 131,072
  factor 13,108 over 8 product 524,280
try 15 shift 18 exp 262,144
  factor 26,215 over 6 product 393,210
try 16 shift 19 exp 524,288
  factor 52,429 over 2 product 131,070
x div 10 -> (x * 52,429) >>(2) 19
  basebits 32 max 3,435,934,515

To divide an u16 by 10 we can multiply by 52,429 then right shift by 19, and we need 32 bits for the multiplication. One can occasionally find these constants in library code that generates decimal representations. Examples:

>>> (12345 * 52429) >> 19
1234
>>> (2020 * 52429) >> 19
202
>>> (1337 * 52429) >> 19
133

199