big numbers in ASM 
Author Message
 big numbers in ASM

POLK schrieb:

Quote:

> Is it possible to generat big numbers in ASM??

How big?
I wrote a library which exports primary operations on long numbers. The
format of these big numbers is similar to the IEEE-standard, only the
mantissas are much longer, up to 2 kBytes.
The exportet functions are
  absolute value
  multiplication by (-1)
  scale (multiplication by 2^n)
  addition
  subtraction
  multiplication of a big number by a unsigned dword
  multiplication of a big number by a big number
  comparision of two big numbers
  copying a big number
  copying a big number and set the destination exponent to zero
  normalization
  denormalization to a particular exponent
  transform signed dword to big number

to allow an application to transform such a number to a string, some
additional BCD-functions are exportet:
  load "one" into big BCD
  multiply big BCD by 2
  multiply big BCD by 2^24
  divide big BCD by 2
  add two big BCD numbers

That are alltogether about 1260 lines of asm-instructions (nasm-syntax)

But all these function are imported by a delphi unit to create more
operations, such as 1/x or sqrt(x), but sqrt(x) doesn't work well (still
looking for the mistake). It's probably possible to write everything in
assembler, but in my opinion the effort is too much.

Quote:
> Thanx.



Wed, 07 Aug 2002 03:00:00 GMT  
 big numbers in ASM
You may "generate" any numbers. If you feel like so, you may program a
math library processing 100-byte-length integer values. :)

Alexei A. Frounze

Quote:

> Is it possible to generat big numbers in ASM??
> Thanx.



Wed, 07 Aug 2002 03:00:00 GMT  
 big numbers in ASM
Alexei A. Frounze schrieb:

Quote:

> Use the following algorithm.

> y0 = x/2 ; x = argument, y = root value on first iteration

> y1 = (y0 + x/y0) / 2
> y2 = (y1 + x/y1) / 2

> repeat this until y(i) = y(i-1) with needed precision.

> Good Luck
> Alexei A. Frounze

What you describe is called "Heron iteration", or however the English
word for the German "Heronisches Iterationsverfahren" is...
Important is that the precision of the temporary results is much higher
than the precision you need.

I tried that myself, and it failed, because there's a mistake somewhere
in my division algorithm which creates an exception only very seldom. I
haven't found it, yet.
But it SHOULD work.

MfG Alexander



Thu, 08 Aug 2002 03:00:00 GMT  
 big numbers in ASM


Quote:

>You're right, i can generate big numbers, but i can't comput root!!
>Does anybody know a mathod???

There is, or was, a WWW page.

Search for a combination of +Rhapson +Karvonen +Buskirk +Juffa

IMHO, every Web page should contain an absolute link to itself or its
home page; this is highly useful in a local *copy*.

--

 Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
 Proper 4-line sig. separator is as above, a line exactly "-- " (SonOfRFC1036)
 Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)



Thu, 08 Aug 2002 03:00:00 GMT  
 big numbers in ASM

Quote:

> What you describe is called "Heron iteration", or however the English
> word for the German "Heronisches Iterationsverfahren" is...
> Important is that the precision of the temporary results is much higher
> than the precision you need.

But I heard it's called "Newton formula". :))

Quote:

> I tried that myself, and it failed, because there's a mistake somewhere
> in my division algorithm which creates an exception only very seldom. I
> haven't found it, yet.
> But it SHOULD work.

Yeah, it really works. I've tried it a lot of times.
For integer root function, code must be tricky.
In details...
Sometimes on the last iterations y(i)=y(i-1) +/- 1. This situation must
be handled respectively. Otherewise, routine hangs. :))

Good Luck
Alexei A. Frounze



Thu, 08 Aug 2002 03:00:00 GMT  
 big numbers in ASM

Quote:



> >You're right, i can generate big numbers, but i can't comput root!!
> >Does anybody know a mathod???

> There is, or was, a WWW page.

> Search for a combination of +Rhapson +Karvonen +Buskirk +Juffa

For square root specifically, you should look into calculating the
inverse square root instead, with a little bit more precision than what
you need for the square root, and then do a single multiplication at the
end.

This works because the Newton iteration for invsqrt() is much sipler
than the one for square root, with no division operations at all!

Terje

--

Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"



Thu, 08 Aug 2002 03:00:00 GMT  
 big numbers in ASM

On 20 Feb 2000 15:48:59 GMT, Alexander Noe

Quote:

>Alexei A. Frounze schrieb:

>> Use the following algorithm.

>> y0 = x/2 ; x = argument, y = root value on first iteration

>> y1 = (y0 + x/y0) / 2
>> y2 = (y1 + x/y1) / 2

>> repeat this until y(i) = y(i-1) with needed precision.

>> Good Luck
>> Alexei A. Frounze

>What you describe is called "Heron iteration", or however the English
>word for the German "Heronisches Iterationsverfahren" is...
>Important is that the precision of the temporary results is much higher
>than the precision you need.

>I tried that myself, and it failed, because there's a mistake somewhere
>in my division algorithm which creates an exception only very seldom. I
>haven't found it, yet.

In the US, at least, it's usually found under Newton/Raphson.  Looks
like Heron is claiming precedence over the English upstart, Newton?

Anyway, it's an obvious technique derived from the very first part of
a Taylor's approximation (picking off just the first order term.)
Derived from this:

  f(x+e) = f(x) + f'(x)*e + (1/2)*f''(e)*(e^2) + ...

Just taking the first part,

  f(x+e) = f(x) + f'(x)*e

and assuming that the function doesn't pose difficulties and that the
terms other than linear are relatively unimportant, then f(x+e) is
zero (given that you are looking for a root, of course.)

Hence,

  f(x+e) = 0 = f(x) + f'(x)*e

and then straight-forwardly,

  e = -f(x)/f'(x)

To use this to solve SQRT(x), you need to first formulate the question
so that you are looking for roots (as suggested above).

If:

  y = x^2

then knowing y and solving for x will get you the SQRT(y).  To
formulate this into a question of solving for roots (zeros), we shape
it this way:

  f(x,y) = 0 = y - x^2

and

  f'(x,y) = -2x dx

Okay, now just pop these into:

  guess(i+1) = guess(i) - f(x,y)/f'(x,y)

or:

  x = x - (y-x^2)/(-2x)
    = x + (y-x^2)/2x
    = (2x^2 + y - x^2) / 2x
    = (x^2 + y) / 2x
    = (1/2) * (x + y/x)

Roughly what was already stated.  And definitely what is called
Newton's method here.

Another technique is to solve for 1/SQRT(x), instead.  If:

  y = x^-2

then knowing y and solving for x will get you the 1/SQRT(y).
Reformulate this into a question of solving for roots (zeros):

  f(x,y) = 0 = y - x^-2

and

  f'(x,y) = 2x^-3 dx

And now, as before:

  guess(i+1) = guess(i) - f(x,y)/f'(x,y)

or:

  x = x - (y - x^-2)/2x^(-3)
    = x - [(y - x^-2) * x^3] / 2
    = x - (y*x^3 - x) / 2
    = (2x - y*x^3 + x) / 2
    = (3x - y*x^3) / 2
    = (1/2) * x * (3 - y*x^2)

Then just multiply the final x computed this way by y to get the
SQRT(y) answer.

These methods work pretty well, so long as you aren't likely to get
trapped looking into the wrong root (if there are several.)  Some
functions, with a poor initial predictor, can also converge very
slowly.  And operating in areas where there are near-zero slopes can
be very bad news.

Jon



Thu, 08 Aug 2002 03:00:00 GMT  
 big numbers in ASM


Quote:

> >You're right, i can generate big numbers, but i can't comput root!!
> >Does anybody know a mathod???

> There is, or was, a WWW page.

> Search for a combination of +Rhapson +Karvonen +Buskirk +Juffa

I think you'll find that there is only one page in the known universe
that would match that search criteria.  (Better use google though --
altavista hasn't visited my page in a while.)  Here's the URL I think you
are referring to.

  http://www.pobox.com/~qed/sqroot.html

This does not address "big numbers".  However if you study the techniques
shown there it should give you a good idea of how to do this.

Quote:
> IMHO, every Web page should contain an absolute link to itself or its
> home page; this is highly useful in a local *copy*.

A good point.  I have too many pages right now, but I will look into
doing this on all my pages.  The problem with using the BASE="..." idea
is that #INDEX URI's don't work properly with it, if I give my redirector
address.  But I could easily put a comment in there somewhere.

--
Paul Hsieh
http://www.pobox.com/~qed/asm.html



Sat, 10 Aug 2002 03:00:00 GMT  
 big numbers in ASM


Quote:

> >Alexei A. Frounze schrieb:
> >> Use the following algorithm.

> >> y0 = x/2 ; x = argument, y = root value on first iteration

> >> y1 = (y0 + x/y0) / 2
> >> y2 = (y1 + x/y1) / 2

> >> repeat this until y(i) = y(i-1) with needed precision.

> >I tried that myself, and it failed, because there's a mistake somewhere
> >in my division algorithm which creates an exception only very seldom. I
> >haven't found it, yet.

You have a few alternatives, if you wish to avoid division.

(1) http://www.azillionmonkeys.com/qed/sqroot.html#accurate (however this
requires that you can do floating point and at least be able to divide by
2 (via a shift or whatever).)

(2) Use some kind of binary search:

// Compute (int)sqrt(v).

x=0;
do {
    for(i=1;(i+x)*(i+x)<v;i+=i);
    i>>=1;
    x+=i;

Quote:
} while( i );

return x;

Ok, so this isn't very fast, but I thought it was clever.  :o)

(3) Compute 2^n/sqrt(v), where 2^n is larger than the desired accuracy.  
Then use the iterator: z := z*(3-z*z*v/2^2n)/2; until z stabilizes, then
compute x := v*z/2^n.  x may be off by a few decimal places (as an
underestimation), so finish it off by concatenating the above algorithm
except remove the "x=0;" line.

Quote:
> >What you describe is called "Heron iteration", or however the English
> >word for the German "Heronisches Iterationsverfahren" is...
> >Important is that the precision of the temporary results is much higher
> >than the precision you need.

> In the US, at least, it's usually found under Newton/Raphson.  Looks
> like Heron is claiming precedence over the English upstart, Newton?

> Anyway, it's an obvious technique derived from the very first part of
> a Taylor's approximation (picking off just the first order term.)
> Derived from this: [...]

That's not necessarily how the algorithm was derived.  For example, I
derived it myself when I was about 14 yrs old, before I knew what
calculus or Taylor's theorem was.  I was sitting with a calculator that
had no square root, and wondered how I could figure out the square root
of a number.  

At first I just used binary search, but that was too slow.  

Then it occurred to me that if I had an approximation x0 to the square
root of v that was too small, then v/x0 would be too large and vice
versa.  So the real square root must be between these two numbers; thus
the average of these numbers must be a better approximation.  This
obviously leads to:

        x <= (x + v/x)/2

Voila.  I suspect Heron first did it this way too.  The algorithm, of
course, converges very rapidly.  Though like me, I doubt Heron could
really explain *why* this algorithm was so much better than binary
search.  Only Newton could explain this ...

--
Paul Hsieh
http://www.pobox.com/~qed/



Sat, 10 Aug 2002 03:00:00 GMT  
 big numbers in ASM


)Alexei A. Frounze schrieb:
)>
)> Use the following algorithm.
)>
)> y0 = x/2 ; x = argument, y = root value on first iteration
)>
)> y1 = (y0 + x/y0) / 2
)> y2 = (y1 + x/y1) / 2
)>
)> repeat this until y(i) = y(i-1) with needed precision.
)>
)> Good Luck
)> Alexei A. Frounze
)
)What you describe is called "Heron iteration", or however the English
)word for the German "Heronisches Iterationsverfahren" is...

That's a reasonable translation, but not the name we use in English. We
call it "Newton's Iteration". In fact, any iteration based on

        Xn+1 = Xn - f(Xn)/f'(Xn)

is called a "Newton's Iteration".

)Important is that the precision of the temporary results is much higher
)than the precision you need.

This is untrue. In fact, it is common to hold the temporary results in
much *less* precision than needed in the final result, as any errors are
self-correting. This can speed the code up quite a bit.

)I tried that myself, and it failed, because there's a mistake somewhere
)in my division algorithm which creates an exception only very seldom. I
)haven't found it, yet.
)But it SHOULD work.
)
)
)MfG Alexander
)

--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel      <- They make me say that.



Sat, 10 Aug 2002 03:00:00 GMT  
 big numbers in ASM


)Yeah, it really works. I've tried it a lot of times.
)For integer root function, code must be tricky.
)In details...
)Sometimes on the last iterations y(i)=y(i-1) +/- 1. This situation must
)be handled respectively. Otherewise, routine hangs. :))

The number of iterations is precomputable. There is no necessity to
compare multibyte numbers, nor to handle unusual termination criteria.

Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel      <- They make me say that.



Sat, 10 Aug 2002 03:00:00 GMT  
 big numbers in ASM

[snip]

)Another technique is to solve for 1/SQRT(x), instead.  If:

[snip]

)Then just multiply the final x computed this way by y to get the
)SQRT(y) answer.

You failed to mention that it is *superior*.

)These methods work pretty well, so long as you aren't likely to get
)trapped looking into the wrong root (if there are several.)  Some
)functions, with a poor initial predictor, can also converge very
)slowly.  And operating in areas where there are near-zero slopes can
)be very bad news.

Points of inflexion are also bad news for Newton's method, regardless of
the value of f'. They can cause the technique to diverge, no matter what
the initial guess.

Getting a good guess for sqrt(.) is very easy, however. Just convert to
floating point, compute the floating point square root, convert back to
integer, and fill the multibyte number with the initial guess.

Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel      <- They make me say that.



Sat, 10 Aug 2002 03:00:00 GMT  
 big numbers in ASM


Quote:



>> >You're right, i can generate big numbers, but i can't comput root!!
>> >Does anybody know a mathod???

>> There is, or was, a WWW page.

>> Search for a combination of +Rhapson +Karvonen +Buskirk +Juffa

>I think you'll find that there is only one page in the known universe
>that would match that search criteria.  

I hoped and expected so.  I believe that it would be slightly better,
though less convenient in this particular case, if no pages matched, as
I think the usual spelling is "Raphson"!  I could be wrong, though.

I've captured that link, in my pc-urls.htm "Algorithms" table.  Thanks.

Quote:
>(Better use google though --
>altavista hasn't visited my page in a while.)  Here's the URL I think you
>are referring to.

>  http://www.pobox.com/~qed/sqroot.html

>This does not address "big numbers".  However if you study the techniques
>shown there it should give you a good idea of how to do this.

My own vast-numbers code, in longcalc.pas, uses the "school" method for
integer square root.  It's all I really understand.

Quote:
>> IMHO, every Web page should contain an absolute link to itself or its
>> home page; this is highly useful in a local *copy*.

>A good point.  I have too many pages right now, but I will look into
>doing this on all my pages.  The problem with using the BASE="..." idea
>is that #INDEX URI's don't work properly with it, if I give my redirector
>address.  But I could easily put a comment in there somewhere.

I put a full reference in the top header, which also colours it (or
...).  For example, one page starts (compressed):
        <BODY><CENTER>&#169; J R Stockton, &gt;= 2000-02-21
        <H1><A HREF="http://www.merlyn.demon.co.uk/delphi.htm">
        Delphi Starting Page</A></H1> * <A HREF="index.htm">Home
        Page</A> * <A HREF="Pascal.htm">Pascal</A> * </CENTER>
That also helps me detect the more careless page-thieves.  But I don't
use complications such as BASE - and have just seen that my local-links-
checker (cheklinx, sigline 3) needs an upgrade to deal with it, or at
least to warn (Fx: editing, testing; latter done) of it.  I know nothing
of #INDEX, though.

--

 Web <URL: http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
 PAS, EXE in <URL: http://www.merlyn.demon.co.uk/programs/> - see 00index.txt.
 Do not Mail News to me.    Before a reply, quote with ">" or "> " (SoRFC1036)



Sat, 10 Aug 2002 03:00:00 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. J with BIG numbers

2. REALLY big numbers

3. Big number

4. Big Numbers

5. UK Developers - BT Big Number source code available

6. Big number package in Eiffel...???

7. big numbers

8. big numbers

9. Big numbers

10. Big number conversion question.

11. SCM Scheme and VERY big numbers

12. Big numbers

 

 
Powered by phpBB® Forum Software