flat assembler
Message board for the users of flat assembler.

Index > Main > memory efficient multiply modulo

Author
Thread Post new topic Reply to topic
b1528932



Joined: 21 May 2010
Posts: 287
b1528932
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.
Post 23 Feb 2011, 17:30
View user's profile Send private message Reply with quote
b1528932



Joined: 21 May 2010
Posts: 287
b1528932
Code:
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?
Post 23 Feb 2011, 17:48
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.