Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
I have to divide large unsigned data. i need quotient and reminder.
so i first must learn basics.
Oposite, multiplication is easy - shift all 1 bits and keep adding to proper offset. Memory requirement is always equal to bits i work on.
But division is hardcore. I never experienced such problems, i stuck literaly for MONTH now, and i dont understand anything about it. i dont get anything, i can stare for hours in code and... nothing comes to my mind.
I have more than few algos for division, but i just cant understand them.
Im interested in straightforward method without fancy optimization (ok, maybe NOT substract loop). How do i divide 1 byte by 1 byte?
I cant do opposite multiplication, shift right and add, i just have no idea how to proceed. If you have an example code it might be usefull if its really basic (c/asm).
I count on your help.
DIVISION
Started by
Guest_h4x_*
, Aug 05 2009 02:21 PM
5 replies to this topic
Back to top|
|
|
#2
Posted 05 August 2009 - 05:42 PM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
C + the GMP library will make this easy.
#3
Guest_h4x_*
Posted 07 August 2009 - 11:27 AM
Guest_h4x_*
Guest_h4x_*
-
- Guests
i know i can use gmp and have this done by just one function.
but i cant use gmp and i cant use c.
my next question is how can i divide very large ammount of data.
i cant find anyone comnetent enought to answer my question.
People are giving me algos with obvious flaws wich i without knowleadge can detect. Or they are so inefficient like substract untill divident < divisor.
i know how to divide large by 64bit, just keep reminder in rdx andd mov to rax next less significant part.
but what about > 64bit divisor? what then?
but i cant use gmp and i cant use c.
my next question is how can i divide very large ammount of data.
i cant find anyone comnetent enought to answer my question.
People are giving me algos with obvious flaws wich i without knowleadge can detect. Or they are so inefficient like substract untill divident < divisor.
i know how to divide large by 64bit, just keep reminder in rdx andd mov to rax next less significant part.
but what about > 64bit divisor? what then?
#4
Posted 08 August 2009 - 05:18 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
You can download the source code for GMP. I believe a lot of it is actually assembler.
#5
Guest_h4x_*
Posted 08 August 2009 - 06:36 AM
Guest_h4x_*
Guest_h4x_*
-
- Guests
yes perhaps very optimized one
i want basics, optimization is easy for me if i understand what to do!
my solution:
1. shift divisor left untill most significant qword is aligned with most signisicant qword of divident.
2. while(divisor <= divident)dividnt -= divisor. quotient is number of substractions, reminder is what left
3. shift 1 qword right (divident) untill you match all data. Use reminder from previous division to extend substraction. continue 2
and yes if i divide by small number i end up with LARGE substraction loop that take ages to complete.
i want basics, optimization is easy for me if i understand what to do!
my solution:
1. shift divisor left untill most significant qword is aligned with most signisicant qword of divident.
2. while(divisor <= divident)dividnt -= divisor. quotient is number of substractions, reminder is what left
3. shift 1 qword right (divident) untill you match all data. Use reminder from previous division to extend substraction. continue 2
and yes if i divide by small number i end up with LARGE substraction loop that take ages to complete.
#6
Posted 11 August 2009 - 01:32 PM
G_Morgan
-
- Members
-
- 537 posts
Programming God
I'm not sure if this does what you want but here is an article on arbitrary precision integers with code
Arbitrary-precision integer arithmetic © - LiteratePrograms
Arbitrary-precision integer arithmetic © - LiteratePrograms
