flat assembler
Message board for the users of flat assembler.
Index
> Main > Large Number 
Author 

revolution
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
Here vid covered various big numbers operations: http://x86asm.net/articles/workingwithbignumbersusingx86instructions/index.html


27 Aug 2008, 02:57 

LocoDelAssembly
Sorry for my usual limited math skills but in http://x86asm.net/articles/workingwithbignumbersusingx86instructions/index.html#Multiplication , is it possible that some ADCs are missing?


27 Aug 2008, 03:13 

vid
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
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:
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
vid wrote:
Yes I was thinking that those "add eax, ecx" should be "add eax, ecx / adc edx, 0". 

27 Aug 2008, 15:27 

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


27 Aug 2008, 17:50 

Zero
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
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. 

27 Aug 2008, 20:49 

bitRAKE
Zero wrote: And lastly, Good job bitRake. I've seen your solutions to other problems, and they are always so elegant and efficient. 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. 

03 Sep 2008, 14:09 

Zero
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
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.


06 Sep 2008, 12:24 

magicSqr
bitRAKE wrote:
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
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
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
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
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
DigitalSystem.pdf was a good explanation of the digital square root algorithm  better algorithms for multilimb 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
CDQ will do it for 2*0xFFFFFFFF right?


13 Nov 2011, 08:09 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.