Re: 2^20991011-1
- To: mathgroup at smc.vnet.net
- Subject: [mg45462] Re: 2^20991011-1
- From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
- Date: Fri, 9 Jan 2004 05:20:29 -0500 (EST)
- Organization: Universitaet Leipzig
- References: <bti1no$a7g$1@smc.vnet.net>
- Reply-to: kuska at informatik.uni-leipzig.de
- Sender: owner-wri-mathgroup at wolfram.com
Hi, perhaps you computer and an english news-group don't like german comments. An other point may be, that with a multi precision arithmetic 2^x_Integer is simply a shift left operation and the -1 need only a simple addition. There are several public domain/open source implementations of multi-precission arithmetic namely http://www.swox.com/gmp/ and you should have a look at this source code Regards Jens Friedrich Laher wrote: > > how can mathematica do that that fast ( 100 seconds on 2.4GHz Athalon ) > while the following needs almost 100 minutes > #include<stdio.h> > /* > Zahl = 2^20 996 011 - 1 get decimal representation, > but > base 10^9 Zahl, 9 dec. digits codes binary in 32Bit. > > 20 996 011*DekadischerLog(2) = 6 320 429, 100 ... > Zahl > has 6 320 431 dec. digits, so needs 702 271 unsigned long's ( of 32 bit ). > > 20 996 011 bit's are 656 125 *32 + 11, 2^11-1 = 2074 > --------------------- > 1 Stunde 38 Min. 3 Sek > -------------------- > */ > unsigned long Zahl[702271], *DezZeiger; > int main() > { > asm(" > # INITIALISIERUNG > > PUSHL %ebx > MOVD %esp,%mm3; LEA Zahl+4*702271,%esp > > MOVL $656125,%ecx > MOVD %ecx,%mm2; MOVL $1,%eax; MOVD %eax,%mm1 > > CLC;CMC; CLD > > LEA Zahl,%edi; MOVD %edi,%mm0 > > MOV $2047,%edx; MOVL $1000000000,%ebx > InitLoop: > SBB %eax,%eax; DIV %ebx; STOSL; LOOP InitLoop; JMP DezStore > > # HAUPTSCHLEIFE > DivLoop: > LODSL; DIVL %ebx > unShortened: > STOSL; LOOP DivLoop > DezStore: > PUSHL %edx > MOVD %mm2,%ecx; TESTL %ecx,%ecx; JE endCalc > > MOVD %mm0,%esi; MOVL %esi,%edi > > LODSL; SUBL %edx,%edx; DIVL %ebx > > TESTL %eax,%eax > JNE unShortened; PSUBD %mm1,%mm2; LOOP DivLoop; JMP DezStore > endCalc: > MOVL %esp, DezZeiger; MOVD %mm3,%esp > POPL %ebx > "); > for(;DezZeiger != Zahl+702271;++DezZeiger)printf("%09u ",*DezZeiger); > > printf("\n"); > }