Author 
Message 
Alexander No #1 / 13

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 IEEEstandard, 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 BCDfunctions 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 asminstructions (nasmsyntax) 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 


Alexei A. Frounz #2 / 13

big numbers in ASM
You may "generate" any numbers. If you feel like so, you may program a math library processing 100bytelength integer values. :) Alexei A. Frounze Quote:
> Is it possible to generat big numbers in ASM?? > Thanx.

Wed, 07 Aug 2002 03:00:00 GMT 


Alexander No #3 / 13

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(i1) 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 


Dr John Stockto #4 / 13

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 4line 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 


Alexei A. Frounz #5 / 13

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(i1) +/ 1. This situation must be handled respectively. Otherewise, routine hangs. :)) Good Luck Alexei A. Frounze

Thu, 08 Aug 2002 03:00:00 GMT 


Terje Mathise #6 / 13

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 selfdiscipline, 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 


Jon Kirwa #7 / 13

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(i1) 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 straightforwardly, 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  (yx^2)/(2x) = x + (yx^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 nearzero slopes can be very bad news. Jon

Thu, 08 Aug 2002 03:00:00 GMT 


Paul Hsi #8 / 13

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 


Paul Hsi #9 / 13

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(i1) 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*(3z*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 


Mike McCar #10 / 13

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(i1) 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 selfcorreting. 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 


Mike McCar #11 / 13

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(i1) +/ 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 


Mike McCar #12 / 13

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 nearzero 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 


Dr John Stockto #13 / 13

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 pcurls.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 vastnumbers 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>© J R Stockton, >= 20000221 <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 pagethieves. But I don't use complications such as BASE  and have just seen that my locallinks 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 


