flat assembler
Message board for the users of flat assembler.

 Index > Main > memory efficient multiply modulo
Author
b1528932

Joined: 21 May 2010
Posts: 287
b1528932 23 Feb 2011, 17:30
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
b1528932

Joined: 21 May 2010
Posts: 287
b1528932 23 Feb 2011, 17:48
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?
23 Feb 2011, 17:48
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum