magic numbers

[dedndave]

sort of
it reverses the 4 bytes of a dword register

Code Select Expand

;EAX = 1A2B3C4Dh

        bswap   eax

;EAX = 4D3C2B1Ah

[RuiLoureiro]

Ok  :t

[RuiLoureiro]

http://www.masmforum.com/board/index.php?topic=17027.msg142029#msg142029

The simplified version...

For divide by 11, the magic reciprocal is  2³² / 11 = 390451572 (remainder 4)
and multiplying by this number gives  12345 * 390451572 = 4820124656340
which doesn't look right, until you realize what we actually did what multiply by 2³² and then divide by 11.
So, for the result, we can just divide by 2³² again - which would be the same as just dividing by 11 in the first place.
Luckily for us, the result of a mul is naturally split into edx and eax, where edx represents the upper part multiplied by 2³², so we just take edx directly as the result.

Sure enough...

12345 / 11 = 1122.27
12345 * 390451572 = 4820124656340 = 1122 * 2³² + 1171350228  => 1122


That's the simplified version because we didn't take the 4 remainder into account, which leads to accumulated errors depending on what values you're dividing. As Dave said, it depends on the range you want to include.
To increase accuracy, you'd shift the magic value and add on a proportion of the remainder. Then shift the result back again to correct for the inherent shift in the magic value, which can effectively give you a few decimal places of accuracy (rounded, naturally.)

Hi Tedd,
               only today i had time to answer you
               thanks for the explanation, i think very good  :t
               i think i have some more questions about this
               one day i will return here, i think
               Thanks, Tedd

[RuiLoureiro]

Tedd,

as far as i understood, the idea behind the so called
"magic numbers" comes from this (it seems):

if we want to divide the integer N by the integer k

we may do this:
                     N       N * f    N        f
                   ----- = ------ = --- * ---- =(N * mn) / f                   
                     k       k * f     f         k

        where mn = f/k

If we use f=2^32 and eax=N, we get the reuslt in edx and
we dont need to divide by f.

Meanwhile, when we want to divide by 2,4,8,16,..., 2^n
we may use shift right to do it instead of div.

In the same way we may replace log(2).

If we have the exponent N2 of base 2 and if we want
the exponent N10 of base 10 we need to solve this:

           2^N2 = 10^N10  =>  N10 = N2 * log(2)

In many cases it seems that it works well if we use f=2^16

                           log(2)*2^16
            N10= N2 ---------------   mn= integer of [log(2)*2^16]
                               2^16

In this case we need to do the shift right to get N10.

Thanks Tedd  :t

[Mikl__]

Bom dia, RuiLoureiro!
Eu escrevi há muito tempo

definition of an integer value log10 can be done without any fyl2x -- try to use integer multiplication of the order on the magic integer constant 4D10h = log10 (2) * 65536
This method is used in the crt_sprintf function.

[dedndave]

it's really simple   :P

let's say we want to divide by 25
rather than dividing by 25, we can multiply by 1/25, and get the same result
however, we cannot easily work with binary fractions
so, we also multiply by a power of 2 (2^N), then divide that same power of 2 out at the end

when we multiply a dword by a dword, we get a result that may be as large as a qword
more accurately, the number of bits in the result will be the number of bits in the multiplier,
plus the number of bits in the multiplicand
anyways, the result of the MUL instruction is always in EDX:EAX
we can divide the result by 2^32 by simply discarding EAX
we lose some precision when we do this, but the bits we discard are usually un-wanted
(actually, you can recover the remainder from these bits)

Code Select Expand

        mov     ecx,X
        mov     eax,1374389535  ;2^35/25
        mul     ecx
        shr     edx,3           ;EDX = quotient

we can multiply the "leftover" bits by the same constant to recover the remainder
however, it's usually faster to multiply the quotient by the divisor, and subtract that from the dividend

Code Select Expand

        imul    eax,edx,25
        sub     ecx,eax         ;ECX = remainder