flat assembler
Message board for the users of flat assembler.

Index > Main > doing math on cpu

Author
Thread Post new topic Reply to topic
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.
Post 03 Jan 2011, 00:51
View user's profile Send private message Reply with quote
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 ???
Post 04 Jan 2011, 06:51
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
same quote. Very Happy
Post 04 Jan 2011, 10:12
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3055
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.
Post 04 Jan 2011, 13:10
View user's profile Send private message Visit poster's website Reply with quote
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).
Post 04 Jan 2011, 18:24
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
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.
Post 04 Jan 2011, 20:34
View user's profile Send private message Visit poster's website 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 GitHub, YouTube, Twitter.

Website powered by rwasa.