Assembly Language - Mathematics WITHOUT maths coprocessor
in [ASM]
|
Prev: HLA wont compile!!
Next: Structs in Assembly
From: ?a/b on 8 Oct 2005 01:23 On Sat, 08 Oct 2005 03:06:35 GMT, "Richard Cooper" <spamandviruses(a)rr.com> wrote: >Pay attention to what it says about how the function takes longer >depending on what numbers you put into it. For example, calculating >log_10(12345678) will take an impossibly long time, but calculating >log_10(1.2345678) will be quite fast, and then you just multiply your i think it is easy to know the integer part of log_2 of a number if "n" is a number [log_2(n)=num_bits_of(n)-1] and from log_2 is possible to know every other log_x (integer part only i presume)
From: ararghmail510NOSPAM on 8 Oct 2005 01:49 On 7 Oct 2005 21:51:09 -0700, "Evenbit" <nbaker2328(a)charter.net> wrote: > >ararghmail510NOSPAM(a)NOW.AT.arargh.com wrote: >[snip] >> In QBasic something like (doesn't converge all that fast): >> >> DEFDBL A-Z >> >> p = 1 >> FOR n = 3 TO 9999999 STEP 4 >> p = p - (1# / n) >> p = p + (1# / (n + 2#)) >> PRINT n, p * 4# >> NEXT n >> >> ' this is for reference: >> PRINT , ATN(1#) * 4# > >Dang!! Is that some new-fangled Super-Extra-High Level Assembler you >are using there??? I can't tell from the syntax which registers you >are using, how many jumps you are making, or which flags you are >testing. :) > >Nathan. OK, here is the asm version: ..nolist Include Bcet.Inc ..list ?ModuleStart Dword pi_Module Byte 'B', 0, 6, 1 Dword 0 Dword 0 @CurSeg Ends ?NumberConst Number_0005 Real8 99999999.0R Number_0007 Real8 4.0R Number_0008 Real8 2.0R Number_0009 Real8 0.7853981633974483R Number_0010 Real8 3.141592653589793R ?UserVars ref_D_v_0 Real8 ? p_D_v_0 Real8 ? n_D_v_0 Real8 ? @CurSeg Ends ..code pi_Module Proc <ForceFrame> fld Real8 Ptr Number_0009 fstp Real8 Ptr ref_D_v_0 fld1 fstp Real8 Ptr p_D_v_0 mov Dword Ptr j_Work_L, 3 fild Dword Ptr j_Work_L jmp FR_01002 FR_01001: fld Real8 Ptr n_D_v_0 fadd Real8 Ptr Number_0007 FR_01002: fst Real8 Ptr n_D_v_0 fld Real8 Ptr Number_0005 externdef h$CMPfp:Proc call h$CMPfp jg FR_01004 FR_01003: fld1 fdiv Real8 Ptr n_D_v_0 fsub Real8 Ptr p_D_v_0 fstp Real8 Ptr p_D_v_0 fld Real8 Ptr n_D_v_0 fadd Real8 Ptr Number_0008 fld1 fdivr fadd Real8 Ptr p_D_v_0 fstp Real8 Ptr p_D_v_0 fld Real8 Ptr n_D_v_0 externdef js$PrintCommaD@0:Proc call js$PrintCommaD@0 fld Real8 Ptr p_D_v_0 fmul Real8 Ptr Number_0007 externdef js$PrintD@0:Proc call js$PrintD@0 fld Real8 Ptr p_D_v_0 fld Real8 Ptr ref_D_v_0 call h$CMPfp jne IF_01006 jmp FR_01004 IF_01005: IF_01006: jmp FR_01001 FR_01004: externdef js$PrintComma@0:Proc call js$PrintComma@0 fld Real8 Ptr Number_0010 call js$PrintD@0 ret pi_Module EndP End You will need the BCET runtime or equiv to use it. :-) -- ArarghMail510 at [drop the 'http://www.' from ->] http://www.arargh.com BCET Basic Compiler Page: http://www.arargh.com/basic/index.html To reply by email, remove the garbage from the reply address.
From: ararghmail510NOSPAM on 8 Oct 2005 01:52 On Sat, 08 Oct 2005 00:49:06 -0500, ararghmail510NOSPAM(a)NOW.AT.arargh.com wrote: >On 7 Oct 2005 21:51:09 -0700, "Evenbit" <nbaker2328(a)charter.net> >wrote: > >> >>ararghmail510NOSPAM(a)NOW.AT.arargh.com wrote: >>[snip] >>> In QBasic something like (doesn't converge all that fast): <snip> >> >>Dang!! Is that some new-fangled Super-Extra-High Level Assembler you >>are using there??? I can't tell from the syntax which registers you >>are using, how many jumps you are making, or which flags you are >>testing. :) >> >>Nathan. >OK, here is the asm version: <snip> Unfortunately, this routine uses the math co-processor, so it doesn't really belong in this thread. :-) -- ArarghMail510 at [drop the 'http://www.' from ->] http://www.arargh.com BCET Basic Compiler Page: http://www.arargh.com/basic/index.html To reply by email, remove the garbage from the reply address.
From: ?a/b on 8 Oct 2005 02:18 On Sat, 08 Oct 2005 03:06:35 GMT, "Richard Cooper" <spamandviruses(a)rr.com> wrote: >On Fri, 07 Oct 2005 15:01:47 -0400, knowledgehungry ><chavanmaheshs(a)yahoo.co.in> wrote: >> Can anybody tell me how to perform >> division without getting divide overflow and WITHOUT using maths >> co-processor using assembly language ? for *integer* big numbers operations for me the reference is the book "Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone" for "float" big numbers i would like to know a reference too ... >Well, the easy way would be the divide instruction. But short of that, >you just have to do long division. > >Say you want to divide 13482 by 234. > >In binary, these are 11010010101010 and 11101010. So it's done like this: > > ________________ > 11101010 ) 11010010101010 > >Then we go here: > > __________1_____ > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > >And then we go here: > > __________11____ > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > -11101010 > ------------- > 100011001010 > >Then we go here: > > __________111___ > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > -11101010 > ------------- > 100011001010 > -11101010 > ------------ > 101111010 > >Then we go like this: > > __________11100_ > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > -11101010 > ------------- > 100011001010 > -11101010 > ------------ > 101111010 > >Then we do like this: > > __________111001 > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > -11101010 > ------------- > 100011001010 > -11101010 > ------------ > 101111010 > -11101010 > --------- > 10010000 > >And then we do this: > > __________111001 R 10010000 > 11101010 ) 11010010101010 > -11101010 > -------------- > 1011101101010 > -11101010 > ------------- > 100011001010 > -11101010 > ------------ > 101111010 > -11101010 > --------- > 10010000 > >And so 13482 divided by 234 is 57 remainder 144. (And how surprised am I >that I didn't screw that up somewhere...) use the word of cpu for perform a division for me is better. i think the division in the book "Handbook of Applied Cryptography" with the base 2^32 is 100x faster than its binary base form
From: Richard Cooper on 8 Oct 2005 05:30
On Fri, 07 Oct 2005 23:57:11 -0400, Evenbit <nbaker2328(a)charter.net> wrote: > This will get you close enough: > > 2378.9396/757.24 But 2083.41 / 663.17 is closer. Once when I was in 8th grade, in math class we were discussing different kinds of numbers. There were the ones like 1/8 whic is 0.125 and then the repeating ones like 1/7 which is 0.142857142857142857... My math teacher made the mistake of saying that you could always tell these numbers apart from numbers that never repeat, because the ones that would repeat would repeat after just a few digits. (Of course, the real way to tell them apart is that fractions always terminate or repeat, it's only things like pi and sqrt(2) and such that never repeat.) Earlier in the year we had been doing stuff with pi, and we were told to use 22/7 as a fraction equal to pi. Now 22/7 is pretty close to pi, but at the age of 11 I had no concept of close enough, so I was determined to do better. I went home and wrote a little program on my TRS-80 to try to find a closer fraction, and I eventually came up with 355/113, which is accurate to six decimal places. I also noticed that unlike 22/7, which repeats after six decimal places, 355/113 didn't appear to repeat at all. So I wrote another program to see how many digits you had to go out before it began repeating. To my complete astonishment, you have to go 112 digits before they start repeating. This had me pretty interested, so I went on to see what other close to pi fractions I could come up with. So then I found 102928/32763. I particularly liked this one since 32763 was close to 32768. This one didn't repeat until after 891 digits, and as an added bonus, was accurate to as many decimal places as my calculator would show. So I made a point to memorize it, and despite it's uselessness, I still remember it to this day. So anyway, when my math teacher said that all repeating numbers will repeat after just a few numbers, I had to bring 102928/32763 to her attention. She found it absolutely amazing. Not because it repeats after 891 digits, but because she thought it was equal to pi. She just typed it into her calculator, it told her it was 3.14159265, and she knew that pi was 3.14159265, and that was all the convincing she needed. She even dug up a poster with the first 10,000 digits of pi on it and showed it to me, telling me that the number on the poster was what that fraction was. I knew that it wasn't, but I just let her go on believing whatever she wanted to believe. Later when I got one of those awful graphing calculators in 9th grade, I found that it had more decimal digits in it's numbers, so then I needed a closer fraction, and came up with 833719/265381, which turned up 3.1415926536 on the graphing calculator, and repeats after 88460 digits. Of course, the pi fractions aren't too useful. Except for 355/113, you end up with more digits in the fraction than the answer is accurate to. However, the many repeating digits are quite interesting. Playing with a simple C program, I've found the fraction x/4294967291 which repeats after 4294967290 digits, so long as 0 < x < 4294967291. Things like this are an easy way to make a simple random number generator, since it gives you 2**32-5 random bits before it repeats. (For this number the length of repeating bits happens to be the same as the length of repeating decimal digits, however that isn't true for all divisors.) A random data generator, in my favorite pseudo-assembly: # ===================================================================== section .text main proc argc, argv, envp mov ecx, 64 * 1024 * 1024 do cld; mov edi, buffer do mov eax, [seed] rol eax, 8 mov edx, eax and eax, 0xFFFFFF00 and edx, 0x000000FF div dword [divisor] mov [seed], edx stosb dec ecx test ecx, 0xFFF loopif nz push ecx sys sys_write, 1, buffer, 4096 pop ecx or ecx, ecx loopif nz return 0 endproc # ===================================================================== section .data seed db 'seed' divisor dd 4294967291 # ===================================================================== section .bss buffer resb 4096 It seems to be perfectly random enough: pj(a)sucks:~/asm$ ./assemble random.asm pj(a)sucks:~/asm$ ./random | hexdump -C -n 256 00000000 64 65 65 74 f5 fa fb 48 cd e6 e8 6c 05 82 8a 1c |deet???H???l....| 00000010 1b 8c b2 8c 89 bf 7c be b0 bd 6f b9 73 b3 2e 9f |..?..?|???o?s?..| 00000020 42 7f e9 1c 4c 7f 8d 8d 7e 7d c3 c3 78 74 d2 d1 |B.?.L...~}??xt??| 00000030 5a 48 1e 16 c3 68 96 71 d1 0a f0 39 15 36 b1 1d |ZH..?h.q?.?9.6?.| 00000040 6a 11 75 93 12 57 4b df 5b b4 7b 5c ca 86 68 cf |j.u..WK?[?{\?.h?| 00000050 f4 a0 0c 0f c7 20 3c 4e e3 a1 2d 8a 72 25 e3 b4 |?..? <N?-.r%?| 00000060 3a bd 72 85 25 b3 3c 99 bc 80 2f 00 ae 80 eb 03 |:?r.%?<.?./.?.?.| 00000070 68 84 97 11 0a 96 f3 55 34 f2 c0 aa 08 bd c3 52 |h.....?U4?*.??R| 00000080 2b b4 d0 9a da 88 13 06 44 a8 5f 1f 57 49 db 9c |+??.?...D?_.WI?.| 00000090 b4 71 4a 0f 86 36 72 4d 9f 10 3b 84 1b 51 29 94 |?qJ..6rM..;..Q).| 000000a0 88 95 cf e6 aa ed 0f 81 56 a1 4d 86 b1 26 83 a1 |..???..V?M.?&.?| 000000b0 75 c0 92 27 4c c2 da c4 7f ce 45 d6 7f 07 5d 30 |u?.'L???.?E?..]0| 000000c0 7b 24 d1 f2 67 b8 19 bc 06 98 80 ac 20 fa 83 5c |{$??g?.?...? ?.\| 000000d0 a4 e4 90 cf 38 76 d4 0c 1a 52 24 3c 83 9a b5 2e |??.?8v?..R$<..?.| 000000e0 92 05 89 e8 da 1b b1 8c 42 8a 77 bd 4c b4 56 b2 |...??.?.B.w?L?V?| 000000f0 7f 85 b1 7c 7d 9c 77 6e 74 0e 55 28 44 47 a9 c9 |..?|}.wnt.U(DG??| 00000100 pj(a)sucks:~/asm$ ./random > random_data pj(a)sucks:~/asm$ ls -la random_data -rw-r--r-- 1 pj users 67108864 2005-10-08 04:52 random_data pj(a)sucks:~/asm$ gzip random_data pj(a)sucks:~/asm$ ls -la random_data.gz -rw-r--r-- 1 pj users 67119134 2005-10-08 04:52 random_data.gz It looks random and it doesn't compress. I'd say that's good enough for just about everything short of cryptography and other things which need truely random numbers. And when I think of some of the god-awful complicated as hell random number routines I've seen in the past... Note the beginning of the data, 'deet', which is 'seed' + 1 backwards. Kind of makes me think there's probably some way to get rid of the divide. |