flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Main > Large Number

Author
Thread Post new topic Reply to topic
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
Post 27 Aug 2008, 02:27
View user's profile Send private message Reply with quote
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.
Post 27 Aug 2008, 02:42
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4634
Location: Argentina

Post 27 Aug 2008, 02:57
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


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?
Post 27 Aug 2008, 03:13
View user's profile Send private message Reply with quote
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
Post 27 Aug 2008, 05:55
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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!!! Smile 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 ebx2   ;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 edx0
  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

nextmov     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. Smile
Post 27 Aug 2008, 07:21
View user's profile Send private message Reply with quote
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".
Post 27 Aug 2008, 15:27
View user's profile Send private message Reply with quote
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...
Post 27 Aug 2008, 17:50
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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?
Post 27 Aug 2008, 20:34
View user's profile Send private message Reply with quote
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.
Post 27 Aug 2008, 20:49
View user's profile Send private message Visit poster's website Reply with quote
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. Smile

Very Happy 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. Wink

_________________
The generation of random numbers is too important to be left to chance - Robert R Coveyou
Post 03 Sep 2008, 14:09
View user's profile Send private message Visit poster's website Reply with quote
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. Smile
Post 04 Sep 2008, 05:08
View user's profile Send private message Reply with quote
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. Laughing

_________________
The generation of random numbers is too important to be left to chance - Robert R Coveyou
Post 06 Sep 2008, 12:24
View user's profile Send private message Visit poster's website Reply with quote
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. Wink



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 Sad

You give a link to

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

that is no longer there Sad

Any ideas where I could find it ¿


Many thanks for any help you can give

magic²
Post 05 Nov 2011, 22:39
View user's profile Send private message Reply with quote
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.
Post 06 Nov 2011, 06:53
View user's profile Send private message Reply with quote
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²
Post 06 Nov 2011, 09:01
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105

btw, again for bitRAKE if he's looking in Wink

You said your factor proc doesn't factor even numbers which is true, but all it would take would be


Code:

proc factornum

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²
Post 06 Nov 2011, 19:16
View user's profile Send private message Reply with quote
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.
Post 07 Nov 2011, 23:55
View user's profile Send private message Reply with quote
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. Wink

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. Razz 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.]

Image
Post 13 Nov 2011, 03:56
View user's profile Send private message Visit poster's website Reply with quote
Overflowz



Joined: 03 Sep 2010
Posts: 1047

CDQ will do it for 2*0xFFFFFFFF right?
Post 13 Nov 2011, 08:09
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >

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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2017, Tomasz Grysztar.