flat assembler
Message board for the users of flat assembler.
 flat assembler > Main > Large Number
Author
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: 15368
Location: 77256 23rd Street
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

Joined: 06 May 2005
Posts: 4634
Location: Argentina
27 Aug 2008, 02:57
LocoDelAssembly

Joined: 06 May 2005
Posts: 4634
Location: Argentina
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: 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.

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

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: 15368
Location: 77256 23rd Street
 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: 2625
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: 2625
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
magicSqr

Joined: 27 Aug 2011
Posts: 105
 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.

 Quote: There is an ever increasing volume of algorithms on my web site.

Excellent algos bitRAKE (sorry I'm about 4 years late, lol).

http://venus.elfak.ni.ac.yu/projects/IMPEG/DigitalSystem.pdf

that is no longer there

Any ideas where I could find it ¿

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
magicSqr

Joined: 27 Aug 2011
Posts: 105
 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
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
magicSqr

Joined: 27 Aug 2011
Posts: 105
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: 2625
Location: dank orb
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: 1047
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----------------Blog General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials 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