Message board for the users of flat assembler.
> Main > memory efficient multiply modulo
I am thinking of a memory efficient way of getting modulo from product of multiplication.
I DO NOT want to store product separatly, i want to combine multiplication and division.
Is that possible?
Lets assume that i have a:
AB * CD % EF
each letter is a radix point
i can do first AB * CD = PRODUCT
and then PRODUCT % EF = REMINDER
this requires me to have a memory for PRODUCT
x is a value that makes it go on new row, eg. 49 = 9 + 4*10, x =10.
I can write this as AB * CD % EF = (A + B*x) * (C + D*x) % (EF) =
(A*C + A*D*x + C*B*x + B*D*x*x) % (EF) =
= (A*C % EF) + (A*D*x % EF) + (C*B*x % EF) + (B*D*x*x % EF)
I have no idea what to do now. Or even if thats possible.
I just want to avoid storing memory for product.
Perhaps i should shift left by power of x? 0 = no shift, 1 = single shift, and so on. then compare with entire EF (zero fill mul result) and if greater subtract. If equal advance lower, if less break. I dont know, my math suck.
Is that possible? Or not. Of course modulus is a large number, not fitting into any hardware solutions.
|23 Feb 2011, 17:30||
914 * 127 mod 2712 (9xx + 1x + 4) * (1xx + 2x + 7) 9xxxx + 18xxx + 63xx + 1xxx + 2xx + 7x + 4xx + 8x + 28 (x/zero = virtual left shift) 90000 + 18000 + 6300 + 1000 + 200 + 70 + 400 + 80 + 28 mod 2712: 504 1728 876 1000 200 70 400 80 28 sum each two 2232 1876 270 480 28 again 4108 750 28 modulo 1396 750 28 2174 mod 2712 = 2174
In theory it looks fine, but 'normally' with memory buffer i just do one modulo cycle. Here i dont know. I belive its compare and after that modulo.
Any ideas how to optimize it?
|23 Feb 2011, 17:48||
< Last Thread | Next Thread >
Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.