magic number division for 64, 32 and 16 bit

[dedndave]

here is a simple program i wrote to test multipliers, with the resultant text output
for the purpose of trying to find an equation, the values that work all the way to FFFFFFFFh aren't helping - lol
i may make them multiple precision to see where they die

[qWord]

to proof your theory you can reduce it to 8bit x 16 bit. If this works, it will also work with 32bit x 64bit.

[dedndave]

i don't think that is really true, qWord
i would like to use simple algebraic statements to determine an equation

the problem, as i see it, is this:
in BASIC, we had a function named INT()
it truncated the fractional part of real number into an integer
this is a natural function in computing, as registers, values, etc have a defined number of bits
when we determine a multiplier, we use this function, as most multipliers have bits that are truncated
also, when we multiply to divide, we use the function again because the multiplication step limits the low-order bits
in algebra, however, there are no simple "rules" for working with this function
if the INT() function appears in an algebraic equation, it is hard to manipulate/evaluate/reduce
perhaps we can somehow define it in a form like this:
R = W + F, where R = a real value, W = the whole part, F = the fractional part
if we can seperate them algebraically, we can manipulate them in an equation
the problem here is how to define algebraically where the whole part ends and the fractional part starts - lol
let me toss it around in my brain for a while

[PBrennick]

dedndave,
What qword said has to be true because the difference between the two is a constant factor of 2x2. In other words
(8*4)*(16*4)=32*64

Paul

[dedndave]

well - it may be that i can derive an equation using smaller registers - that is true

to proof your theory you can reduce it to 8bit x 16 bit. If this works, it will also work with 32bit x 64bit.

the problem with qWords statement is....
i don't have a theory, yet   :lol

[raymond]

If you are talking about multiplying an integer by a reciprocal instead of dividing by an integer, consider this:

- The size of the integer divisor is totally immaterial. Its reciprocal can be computed with an infinite number of decimal places with full precision. That reciprocal is a fraction, whether it be in decimal or binary.
- The number of significant digits (precision) in the product of an integer by a fraction will be dependant on the number of significant digits retained in the fraction.

In other words, if you have a 10 digit integer and you multiply it by a fraction having only 5 significant digits, the result will only be precise to 5 significant digits. The number of significant digits in the multiplying fraction must thus have as many significant digits as the integer being multiplied to result in full precision. (In binary, digit = bit)

Similarly, the precision of the product of an integer by a fraction will not be any more precise by using more digits than necessary in the fraction. As an example, if you need the circumference of a circle whose diameter is given with 3 significant digits, using a value of pi with 4 significant digits would be sufficient, The result would not be any more precise by using a value of pi with 30 significant digits.

[dedndave]

that makes sense, Raymond
more or less - lol
so - if i have a 57 bit maximum dividend, i need a 57 bit multiplier ?
that makes it easy

what about this....
i have a 62 bit maximum dividend
after the multiplication, i shift right 29 bits (essentially, "unneccessary resolution")
i have a 33 bit maximum quotient
does this mean i can get away with a 33 bit multiplier ? (62-29=33)

if i understand what you are saying, it is the size of the quotient that determines the required multiplier resolution
(which would also mean - the divisor does make a difference - larger divisor -> smaller quotient)

this seems to make sense
i can speed up my routine by not using a full 64x64 multiplication
i will see what i can come up with and test it

[dedndave]

ok - we have a theory, now - lol
not only should the multiplier have as many bits as the max quotient, but....

Dave's Theory #1 (assuming it will change - lol)
The minimum multiplier should be equal to or greater than the maximum expected quotient.

[PBrennick]

Hey Dave,

Good luck with your project. I am extremely interested.

btw - theories often give birth to theorems...

Paul

[dedndave]

thanks Paul - well - "Dave's Multiplier Theory #1" looks great on paper
it may wind up on a roll in the bathroom - lol

[PBrennick]

S-o-o-o,

Either way it will prove useful; sounds like a win-win situation. ::)

Paul

[dedndave]

ok - scratch Dave's Multiplier Theory #1 - lol
i have a good handle on it, now
i just need to state it mathematically

[dedndave]

here is a case that never makes it to FFFF_FFFF_FFFF_FFFF
i am dividing by 1,000,000,000
i am using a multiplier of 8970_5F41_36B4_A598 and a shift of 29 (which is really /2^93)

                             HiA LoA
                          X  HiB LoB
                     ------------------

    2^96        2^64        2^32        2^0
                           LoALoB1     LoALoB0
               HiALoB1     HiALoB0
               LoAHiB1     LoAHiB0
   HiAHiB1     HiAHiB0

Multiplier: 89705F41_36B4A598  Shift: 29  Fail: AA4EA381_AE3507FF

A: 89705F41_36B4A598
B: AA4EA381_AE3507FF

carry:    1           2
                           253A1DA9    06F01A68
               5D86D94C    DFFEA8BF
               2464C3F1    FAC73998
   5B6ED745    FE1462C1
-------------------------------------------------
   5B6ED746    80000000    00000000    06F01A68

  5B6ED746_80000000 / 2^29 = 2_DB76_BA34

  result: 2_DB76_BA34   (5B6ED746_80000000 / 2^29)
expected: 2_DB76_BA33   (AA4EA381_AE3507FF / 1,000,000,000)

in this specific application, my maximum dividend is 3B9A_CA03_4B82_FA17, so i am ok
but, the multiply-to-divide should work all the way to at least FFFF_FFFF_FFFF_FFFE
i can't make any of our statements about multiplier resolution work for me, here

[dedndave]

here is the test program and data (it takes a while to run - lol)
notice that there is little or no logic in the failure pattern as i shift the multiplier right

Multiplier: 89705F41_36B4A598  Shift: 29  Fail: AA4EA381_AE3507FF
Multiplier: 44B82FA0_9B5A52CC  Shift: 28  Fail: AA4EA381_AE3507FF
Multiplier: 225C17D0_4DAD2966  Shift: 27  Fail: AA4EA381_AE3507FF
Multiplier: 112E0BE8_26D694B3  Shift: 26  Fail: AA4EA381_AE3507FF
Multiplier: 089705F4_136B4A5A  Shift: 25  Fail: 0F9B0B1C_F79815FF
Multiplier: 044B82FA_09B5A52D  Shift: 24  Fail: 0F9B0B1C_F79815FF
Multiplier: 0225C17D_04DAD297  Shift: 23  Fail: 035E36C8_CDE0B3FF
Multiplier: 0112E0BE_826D694C  Shift: 22  Fail: 014FB4D0_15340DFF
Multiplier: 0089705F_4136B4A6  Shift: 21  Fail: 014FB4D0_15340DFF
Multiplier: 0044B82F_A09B5A53  Shift: 20  Fail: 014FB4D0_15340DFF
Multiplier: 00225C17_D04DAD2A  Shift: 19  Fail: 00390AF2_316B81FF
Multiplier: 00112E0B_E826D695  Shift: 18  Fail: 00390AF2_316B81FF
Multiplier: 00089705_F4136B4B  Shift: 17  Fail: 000D340E_991957FF
Multiplier: 00044B82_FA09B5A6  Shift: 16  Fail: 00053444_56AAADFF
Multiplier: 000225C1_7D04DAD3  Shift: 15  Fail: 00053444_56AAADFF
Multiplier: 000112E0_BE826D6A  Shift: 14  Fail: 0001852A_D5DF1BFF
Multiplier: 00008970_5F4136B5  Shift: 13  Fail: 0001852A_D5DF1BFF
Multiplier: 000044B8_2FA09B5B  Shift: 12  Fail: 00006591_D3EA21FF
Multiplier: 0000225C_17D04DAE  Shift: 11  Fail: 000028FC_FA86ADFF
Multiplier: 0000112E_0BE826D7  Shift: 10  Fail: 000028FC_FA86ADFF
Multiplier: 00000897_05F4136C  Shift:  9  Fail: 00000C1B_356D35FF
Multiplier: 0000044B_82FA09B6  Shift:  8  Fail: 00000C1B_356D35FF
Multiplier: 00000225_C17D04DB  Shift:  7  Fail: 00000C1B_356D35FF
Multiplier: 00000112_E0BE826E  Shift:  6  Fail: 000001D3_0EEADBFF
Multiplier: 00000089_705F4137  Shift:  5  Fail: 000001D3_0EEADBFF
Multiplier: 00000044_B82FA09C  Shift:  4  Fail: 0000006A_675299FF
Multiplier: 00000022_5C17D04E  Shift:  3  Fail: 0000006A_675299FF
Multiplier: 00000011_2E0BE827  Shift:  2  Fail: 0000006A_675299FF
Multiplier: 00000008_9705F414  Shift:  1  Fail: 0000000E_E6B27FFF
Multiplier: 00000004_4B82FA0A  Shift:  0  Fail: 0000000E_E6B27FFF

[raymond]

According to qWord's dialog box, the multiplier should be 89705F4136B4A597h (instead of 89705F4136B4A598h) and you then need to increment the dividend before the multiplication.

You then get the expected result.