flat assembler
Message board for the users of flat assembler.

 Index > Main > Large Number
Author
Zero

Joined: 02 Aug 2008
Posts: 16
Zero 27 Aug 2008, 02:27
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: 19742
Location: In your JS exploiting you and your system
revolution 27 Aug 2008, 02:42
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 compare-subtract-shift, 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: 4624
Location: Argentina
LocoDelAssembly 27 Aug 2008, 02:57
27 Aug 2008, 02:57
LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 27 Aug 2008, 03:13
Sorry for my usual limited math skills but in http://x86asm.net/articles/working-with-big-numbers-using-x86-instructions/index.html#Multiplication , is it possible that some ADCs are missing?
27 Aug 2008, 03:13
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 27 Aug 2008, 05:55
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
Zero 27 Aug 2008, 07:21
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
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

jmp     next

n1:     cmp     ebx,99
jle     @f
jmp     n2

jmp     next

n2:     cmp     ebx,999
jle     @f
jmp     n3

jmp     next

n3:     cmp     ebx,9999
jle     @f
jmp     n4

jmp     next

n4:     cmp     ebx,99999
jle     @f
jmp     n5

jmp     next

n5:     cmp     ebx,999999
jle     @f
jmp     n6

jmp     next

n6:     cmp     ebx,9999999
jle     @f
jmp     n7

jmp     next

n7:     cmp     ebx,99999999
jle     @f
jmp     n8

jmp     next

n8:     cmp     ebx,999999999
jle     @f
jmp     more

jmp     next

next: mov     byte [esi],32
jmp     begin

yes:
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: 4624
Location: Argentina
LocoDelAssembly 27 Aug 2008, 15:27
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: 7105
Location: Slovakia
vid 27 Aug 2008, 17:50
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
Zero 27 Aug 2008, 20:34
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: 19742
Location: In your JS exploiting you and your system
revolution 27 Aug 2008, 20:49
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: 3849
Location: vpcmipstrm
bitRAKE 03 Sep 2008, 14:09
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.

_________________
¯\(°_o)/¯ The hardcore cynic mistakes good for guile.
03 Sep 2008, 14:09
Zero

Joined: 02 Aug 2008
Posts: 16
Zero 04 Sep 2008, 05:08
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: 3849
Location: vpcmipstrm
bitRAKE 06 Sep 2008, 12:24
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.

_________________
¯\(°_o)/¯ The hardcore cynic mistakes good for guile.
06 Sep 2008, 12:24
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 05 Nov 2011, 22:39
bitRAKE wrote:

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.

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
Tyler 06 Nov 2011, 06:53
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
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 06 Nov 2011, 09:01
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
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 06 Nov 2011, 19:16
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)
.
.
.
.
.
.
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
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 07 Nov 2011, 23:55
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
bitRAKE

Joined: 21 Jul 2003
Posts: 3849
Location: vpcmipstrm
bitRAKE 13 Nov 2011, 03:56
DigitalSystem.pdf was a good explanation of the digital square root algorithm -- better algorithms for multi-limb numbers in GMP, and modern FPUs are faster. Once you understand how to do the square root of a two bit number then the rest is just shifting and addition.

Also, I remember reading something about a square root algorithm which tracked errors and adjusted the result in a final pass. Seems like it'd work great on very large numbers.

Algorithm should be used with a sieve (more shameless self promotion). I thought it a great feature that is pulls out prime powers. Posit's reply is a good explanation of the algorithm. While playing with some geometry I rediscovered the method.

[People message me all the time from Project Euler asking how to learn x86. Of course, I always send them here. Sites says I haven't solved a problem in 1980 days, lol -- guess I should get back in the top ten Assembly solvers.]

13 Nov 2011, 03:56
Overflowz

Joined: 03 Sep 2010
Posts: 1046
Overflowz 13 Nov 2011, 08:09
CDQ will do it for 2*0xFFFFFFFF right?
13 Nov 2011, 08:09
 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