
Author 
Thread 


Zero
Joined: 02 Aug 2008
Posts: 16

Large Number
hello everyone
I have a question regarding large numbers. I was experimenting with numbers and mathematical equations as a method to help me learn more assembler. And so, it popped into my mind that I wanted to divide a very large number by a small number just for the hell of it. The number I chose just happened to be 895052476137.
Then I remembered, that from what I understand about assembly programming, the largest number that can be loaded into a 32 bit register is FFFFFFFF(unsigned of course) which is equivalent to 4294967295. But as you can see, the number I chose is greater than this limit.
Could someone please provide an example of how to work with super large numbers, specifically division and multiplication. In particular, the equation I am simulating requires repeated division and multiplication by other numbers, and so the results I obtain are still too large to fit in a 32 bit register.
My apologies in advance if this question is somehow inappropriate or silly. I'm still very new to assembly programming and I'm trying my best to learn and even though I've read the documentation, some of it is still too esoteric for me.
thanks

27 Aug 2008, 02:27 

revolution
When all else fails, read the source
Joined: 24 Aug 2004
Posts: 15549
Location: The total perspective vortex

Zero: I think what you need to read about is arbitrary precision mathematics (google it). There are a lot of references available and many bits of sample code around (in C, but should be readable for an assembly coder).
The basic idea is to use multiple registers/memory locations to hold the numbers. And to use extended precision routines to perform the various computations. ADD and SUB are quite simple by just rippling the carry through. MUL is just the extended cross multiply you learned in school (for small numbers at least). DIV can be done with comparesubtractshift, just like long division you learn at school, but there are some higher level algorithms that can do the job faster.
I suggest to start simple with ADD and SUB and work your way up.

27 Aug 2008, 02:42 

LocoDelAssembly
Your code has a bug
Joined: 06 May 2005
Posts: 4634
Location: Argentina


27 Aug 2008, 02:57 

LocoDelAssembly
Your code has a bug
Joined: 06 May 2005
Posts: 4634
Location: Argentina


27 Aug 2008, 03:13 

vid
Verbosity in development
Joined: 05 Sep 2003
Posts: 7109
Location: Slovakia

ADCs where? In multiplication, we don't carry just one bit. Carried part is in EDX.
You mean if result overflows when the carried part is added? hmmm

27 Aug 2008, 05:55 

Zero
Joined: 02 Aug 2008
Posts: 16

Wow...thanks guys! That was exactly what I was looking for. The reason I needed it was to solve problem # 4 from Project Euler. And I finally solved it!!! I won't give the answer away in case someone else also wants to solve it.
Problem:
Quote: 
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?


Also, below is the program I wrote to find the answer. I would like some suggestions on how to improve it and optimize it. It looks really ugly right now and I'm sure there are places that are COMPLETELY inefficient.
In particular the speed. When I run the program, it takes almost one minute to show the MessageBox with the answer!!! That is really slow.
Code: 
format PE GUI 4.0
entry start
include '%fasminc%\win32a.inc'
include 'last.inc'
include 'factor.inc'
section '.data' data readable writeable
bignum dd 0xE589EAC7
dd 0x8B
dd 0
temp dd 0
dd 0
dd 0
hello db 'Answer',0
sresult rb 20
section '.code' code readable writeable
start:
mov ebx, 2 ;divisor
mov esi,sresult
begin: cmp ebx,0xFFFFFFFF
jae exit
mov ecx,[bignum+8]
mov [temp+8],ecx
mov ecx,[bignum+4]
mov [temp+4],ecx
mov ecx,[bignum]
mov [temp],ecx
mov edx, 0
mov eax, [bignum+8] ;EDX:EAX = number to divide
div ebx
mov [bignum+8], eax
mov eax, [bignum+4]
div ebx
mov [bignum+4], eax
mov eax, [bignum]
div ebx
mov [bignum], eax
test edx,edx
jne yes
push ebx
push esi
stdcall int2a
cmp ebx,9
jle @f
jmp n1
@@: add esi,1
jmp next
n1: cmp ebx,99
jle @f
jmp n2
@@: add esi,2
jmp next
n2: cmp ebx,999
jle @f
jmp n3
@@: add esi,3
jmp next
n3: cmp ebx,9999
jle @f
jmp n4
@@: add esi,4
jmp next
n4: cmp ebx,99999
jle @f
jmp n5
@@: add esi,5
jmp next
n5: cmp ebx,999999
jle @f
jmp n6
@@: add esi,6
jmp next
n6: cmp ebx,9999999
jle @f
jmp n7
@@: add esi,7
jmp next
n7: cmp ebx,99999999
jle @f
jmp n8
@@: add esi,8
jmp next
n8: cmp ebx,999999999
jle @f
jmp more
@@: add esi,9
jmp next
more: add esi,10
next: mov byte [esi],32
add esi,1
jmp begin
yes:
add ebx,1
mov ecx,[temp+8]
mov [bignum+8],ecx
mov ecx,[temp+4]
mov [bignum+4],ecx
mov ecx,[temp]
mov [bignum],ecx
jmp begin
exit:
invoke MessageBox,NULL,sresult,hello,MB_OK
invoke ExitProcess,0
ret
section '.idata' import data readable writeable
library KERNEL32, 'KERNEL32.DLL',\
USER32, 'USER32.DLL'
import KERNEL32,\
ExitProcess, 'ExitProcess'
import USER32,\
MessageBox, 'MessageBoxA'


And lastly, Good job bitRake. I've seen your solutions to other problems, and they are always so elegant and efficient.

27 Aug 2008, 07:21 

LocoDelAssembly
Your code has a bug
Joined: 06 May 2005
Posts: 4634
Location: Argentina

vid wrote: 
You mean if result overflows when the carried part is added? hmmm


Yes I was thinking that those "add eax, ecx" should be "add eax, ecx / adc edx, 0".

27 Aug 2008, 15:27 

vid
Verbosity in development
Joined: 05 Sep 2003
Posts: 7109
Location: Slovakia

Loco: not sure if that can happen, but you may be right. can't think right now...

27 Aug 2008, 17:50 

Zero
Joined: 02 Aug 2008
Posts: 16

Hmm, I still don't understand why it takes so long to display the MessageBox. I know I am doing lots of divisions and copying into memory etc, but I thought for such a small program that it would still run fast.
From project euler, other people's programs are running in milliseconds, and although I'm doing a brute force solution that isn't the best, I don't see how it's different from many of the other solutions that were posted.
Any ideas?

27 Aug 2008, 20:34 

revolution
When all else fails, read the source
Joined: 24 Aug 2004
Posts: 15549
Location: The total perspective vortex

Zero wrote: 
Hmm, I still don't understand why it takes so long to display the MessageBox. I know I am doing lots of divisions and copying into memory etc, but I thought for such a small program that it would still run fast.
From project euler, other people's programs are running in milliseconds, and although I'm doing a brute force solution that isn't the best, I don't see how it's different from many of the other solutions that were posted.
Any ideas?


Take notice of your loops. Obviously the more times you do something the longer it takes. Try stepping through one instruction at a time with a debugger and then you should get an understanding of just how much work the CPU has to do.

27 Aug 2008, 20:49 

bitRAKE
Joined: 21 Jul 2003
Posts: 2628
Location: dank orb

Zero wrote: 
And lastly, Good job bitRake. I've seen your solutions to other problems, and they are always so elegant and efficient.


I meet so many people from my posts there  it surprised me when the site took off the way it did.
It is possible to factor a number without division or multiplcation! (shameless self reference) Oddly enough this method finds the large factors first as well.
_________________ The generation of random numbers is too important to be left to chance  Robert R Coveyou

03 Sep 2008, 14:09 

Zero
Joined: 02 Aug 2008
Posts: 16

Damn, that's a sweet algorithm. I had no idea you could do it without division/multiplication. Initially, I had some difficulty understanding what you were doing, but I think I understand it now for the most part.
Btw, I noticed you've solved around 90 of the Project Euler problems but none of the more recent ones. I hope you haven't given up on the site. It's good assembly programming practice and the problems are fun.....and also....I've learned a lot of tricks/strategies just from studying your assembly code....as I'm sure others have as well....so it'd be nice if you kept on going.

04 Sep 2008, 05:08 

bitRAKE
Joined: 21 Jul 2003
Posts: 2628
Location: dank orb

I haven't given up on the site  the problems just moved beyond the time I had to invest in them. Lately, I can't even get a moment alone to rub two thoughts together.
_________________ The generation of random numbers is too important to be left to chance  Robert R Coveyou

06 Sep 2008, 12:24 


from the above link
Quote: 
There is an ever increasing volume of algorithms on my web site.


Excellent algos bitRAKE (sorry I'm about 4 years late, lol).
Can find your blog but not your website
You give a link to
http://venus.elfak.ni.ac.yu/projects/IMPEG/DigitalSystem.pdf
that is no longer there
Any ideas where I could find it ¿
Many thanks for any help you can give
magic²

05 Nov 2011, 22:39 

Tyler
Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

You might want to look at GMP once you're done. They have (presumably) optimized assembly versions of multiplication and division for arbitrary precision integers. It would be a good way to get feedback as to how to improve your technique.

06 Nov 2011, 06:53 


Tyler wrote: 
You might want to look at GMP once you're done.


Hi Tyler.
I'm already using GMP and you're correct (afaik) that they are very well optimized. However, there are some parts of the code I'm writing where I know that particular integers will never exceed an unsigned dword. In these cases, GMP would actually be slower as it would still have to go from the pointer to the number and check how many limbs it has etc., whereas, I would be able to bypass that.
magic²

06 Nov 2011, 09:01 


btw, again for bitRAKE if he's looking in
You said your factor proc doesn't factor even numbers which is true, but all it would take would be
Code: 
proc factor, num
bsf ecx, [num]
push ecx
shr [num], cl ;now we have num = num/(2^ecx), which is odd (but not strange)
.
.
.
your code
.
.
.
pop ebx
retn 4


so your 2 factors are returned in eax and edx. and num is also divisible by 2^ebx
magic²

06 Nov 2011, 19:16 


just noticed your proc returns prime² as a prime.
i.e num=9 > eax=1, edx=9
num=25 > eax=1 edx=25 etc.

07 Nov 2011, 23:55 


CDQ will do it for 2*0xFFFFFFFF right?

13 Nov 2011, 08:09 



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








