flat assembler
Message board for the users of flat assembler.

 Index > Main > doing math on cpu
Author
b1528932

Joined: 21 May 2010
Posts: 287
b1528932
im interested in some mathematical problems that can be solved using cpu, and how to do it.

for example, to add 2 values, i must xor each bit from second one with corresponding bit of first one, and xor-if-carry ani ghgher bit untill there is no carry. Same substraction.

There are instructions that optimize this by doing it on hardware level, for example add/adc and sub/sbb.

Is there any faster way of doing simple math using hardware inbstead of extensive algos using xor?

What about multiplication? I have to do repeated addition and left shift, or use mul instruction and repeated addition. I belive that mul/addition is (much?) more efficient, especially if seocnd operand (x*y, x = 1st, y = 2nd) contain many 1 (because i have to shift per each bit set). Mul takes fixed ammount of bytes, and manage it regardless of its contents.

Division cant be dont using div, right? Or theren is a way? I have to do some sort of binary division, basicly repeated substraction. I can optimize (wich is a key here) by shifting 2nd operand to match left side value in position. Unfortunatly i have to do bit-by-bit or there is no point in making (DWORD)-1 loops in worst case scenario...
Is there a way to optimize division, preferably using intended div instruction? imul/idiv i belive cant be used in larde operations because they to same as mul/div but they mask off 7th bit (instead of using it to * or \, they xor bits from operands and write result).

Do you know some usefull tricks i can use? Is using FPU generally wrong idea? Does mmx or sse or anything else newer capable of efficient math? How does gpu do calculations?
I want for example to do multiple multiplications and divisions, ehat does matter when it come to speed? Lets say i want to bruteforce rsa1024 private key, i need to find p and q. And to do it, i need to test every possible vlaue they might have. How to i start? I wont actually do this because its carzy even for me, but its a start... When i build my giga-cluster some day i want to be ready.
03 Jan 2011, 00:51
nop

Joined: 01 Sep 2008
Posts: 165
Location: right here left there
nop
i dont get it
what do you have against cpu instructions add adc sub sbc mul imul div idiv
or fpu instructions fadd etc ???
why do you want to do it the hard way using binary logic ???
04 Jan 2011, 06:51
edfed

Joined: 20 Feb 2006
Posts: 4240
Location: 2018
edfed
same quote.
04 Jan 2011, 10:12
bitRAKE

Joined: 21 Jul 2003
Posts: 3018
Location: vpcmipstrm
bitRAKE
The top post should be prefixed with the notion of multi-precision math.

There are some posts on the board regarding the topic.

Might want to look into the GMP project.
04 Jan 2011, 13:10
b1528932

Joined: 21 May 2010
Posts: 287
b1528932
Imul/div/idiv cant be used when my operand is higher than register size.

I want to calculate large nimbers, thousands, hundreds of thousands of bits, by performing multiple operations on them, and i need a template how to design it.
Now i got this:

- addition, result is also operant one, second operand must be no-greater than first. First operand is overwritten. First operand space must contain additional unit (dword?) to contain carry, although i cant figure out if it wouldnt be better just to indicate carry in other manner.
- substraction exactly same as division, although i must check upper boundary when carrying.
- multiplication - result is first operand, and its overwritten. Result = size of both operands. third operand might indicate signed or unsigned operation.
- division, here i definitly need way of indicateng divide-by-0, first operand is reminder, second must be no-greater in bits than first, third is quotient. fourth operand might be used to indicate divide-by-0, and if i want to perform modulo, division, or both. And possibly signed/unsigned.
i addition/substraction i might use 3rd arg to present carry to caller, although i might use extended first operand rule, i havent decided yet.

My goal is to make library of functions working on 16, 32 and 64 bit environments, supporting both big and little endian positioning. Those function must be sufficient to perform any mathem,atical task with relative ease, just calling a function with arguments. I want for start to have add/sub/mul/div/idiv/imul, then i will try to make some geometrical functionsa like sinus and tangent. After then, i dont know, what else will be requiret, i appreciate your proposals what to do (anfd maybe how).
04 Jan 2011, 18:24
edfed

Joined: 20 Feb 2006
Posts: 4240
Location: 2018
edfed
implement just addition and substractions on large number, and after, devellop mul and div on these.
X*Y = X+X+X+ [Y times]
X/Y = (X=X-Y) until X lower or equal.
first make it work, second, make it work fast.
04 Jan 2011, 20:34
 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