www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Has anyone made that BigInteger class

reply hellcatv hotmail.com writes:
I was thinking of using D for one of my projects--the problem is that BigInteger
is a vital component for it...

has anyone implemented BigInt in D itself and could point me to a link? I'd be
much obliged--I'm not sure implementing BigInt myself is my cuppa joe^H^H^Htea.
May 24 2004
next sibling parent "KTC" <me here.com> writes:
 has anyone implemented BigInt in D itself and could point me to a link?

"Arcane Jill" posted a few days ago saying (s)he was writing one and that (s)he expected to finish it in a week or two... KTC -- Experience is a good school but the fees are high. - Heinrich Heine
May 24 2004
prev sibling next sibling parent Arcane Jill <Arcane_member pathlink.com> writes:
In article <c8u62s$1fh9$1 digitaldaemon.com>, hellcatv hotmail.com says...
I was thinking of using D for one of my projects--the problem is that BigInteger
is a vital component for it...

has anyone implemented BigInt in D itself and could point me to a link? I'd be
much obliged--I'm not sure implementing BigInt myself is my cuppa joe^H^H^Htea.

May 25 2004
prev sibling parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c8u62s$1fh9$1 digitaldaemon.com>, hellcatv hotmail.com says...
I was thinking of using D for one of my projects--the problem is that BigInteger
is a vital component for it...

has anyone implemented BigInt in D itself and could point me to a link? I'd be
much obliged--I'm not sure implementing BigInt myself is my cuppa joe^H^H^Htea.

Yes, me. I'm releasing it next week. It's destined to be called "etc.bigint". Right now it's still in development. Everything works, but I've got a couple more high level functions to add, and a little bit of optimizing and profiling to do. Can you wait a week? What do you need it FOR, by the way? I'll be doing a crypto library next, so if you want it for cryptography you could just wait even longer (or collaborate). Arcane Jill
May 25 2004
next sibling parent reply Daniel Horn <hellcatv hotmail.com> writes:
Hi-
Actually I'm on a bit of a time budget here... so if you could send it t 
o me sooner I'd be much obliged (the hotmail addy is fine).
I only need +,-,*,/,%

I'd also help you beta test it.

I'm writing a ray tracer that is very precise (keeps track of 
intersections at rational locations)
It seems silly, but I can give you more motivational details when it's 
done. basically it's verifying the potential of using a ray tracer for 
more than raytracing ;-)
Currently I'm checkin it into dsource.org (project deliria)

--Daniel

Arcane Jill wrote:
 In article <c8u62s$1fh9$1 digitaldaemon.com>, hellcatv hotmail.com says...
 
I was thinking of using D for one of my projects--the problem is that BigInteger
is a vital component for it...

has anyone implemented BigInt in D itself and could point me to a link? I'd be
much obliged--I'm not sure implementing BigInt myself is my cuppa joe^H^H^Htea.

Yes, me. I'm releasing it next week. It's destined to be called "etc.bigint". Right now it's still in development. Everything works, but I've got a couple more high level functions to add, and a little bit of optimizing and profiling to do. Can you wait a week? What do you need it FOR, by the way? I'll be doing a crypto library next, so if you want it for cryptography you could just wait even longer (or collaborate). Arcane Jill

May 25 2004
parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c904uv$1skt$1 digitaldaemon.com>, Daniel Horn says...
Hi-
Actually I'm on a bit of a time budget here... so if you could send it t 
o me sooner I'd be much obliged (the hotmail addy is fine).
I only need +,-,*,/,%

Hi, Not really, I'm afraid. All there is left for me to do now is wrapping it up, adding documentation, licensing (BSD-style) and so on. To be honest, it would take almost as long to wrap it up for you as for everybody else. Today is Wednesday. The package will be ready sometime over the weekend. If that's really not soon enough for your time budget then you can always use the gmp library (Gnu Multi-Precision) in C. Sorry, but, I'm an artist. Things will be ready when they are ready. That's all I can say. Arcane Jill
May 27 2004
next sibling parent Ben Hinkle <bhinkle4 juno.com> writes:
 Today is Wednesday. The package will be ready sometime over the weekend.
 If that's really not soon enough for your time budget then you can always
 use the gmp library (Gnu Multi-Precision) in C.

If you do want to use GMP I've already made the D interface file and object wrappers. Get them at code: http://home.comcast.net/~benhinkle/gmp-d/gmp-d.zip documentation: http://home.comcast.net/~benhinkle/gmp-d/doc/
May 27 2004
prev sibling parent Daniel Horn <hellcatv hotmail.com> writes:
Arcane Jill wrote:
 In article <c904uv$1skt$1 digitaldaemon.com>, Daniel Horn says...
 
Hi-
Actually I'm on a bit of a time budget here... so if you could send it t 
o me sooner I'd be much obliged (the hotmail addy is fine).
I only need +,-,*,/,%

Hi, Not really, I'm afraid. All there is left for me to do now is wrapping it up, adding documentation, licensing (BSD-style) and so on. To be honest, it would take almost as long to wrap it up for you as for everybody else. Today is Wednesday. The package will be ready sometime over the weekend. If that's really not soon enough for your time budget then you can always use the gmp library (Gnu Multi-Precision) in C. Sorry, but, I'm an artist. Things will be ready when they are ready. That's all I can say. Arcane Jill

Well I can't argue with that--we all have our own schedules :-) Ok I can wait until the weekend. I'll try to use a ulong for now and then use your BigInteger as a drop in replacement (I'll templatize everything) And if necessary I'll use that C Wrapper--but having everything in native D will make this more beautiful. Soon D will have it's own raytracer... the most accurate ray tracer in the west-- probably also the slowest ;-) but hey..for what I'm doing I can't lose a decimal without disasterous consequences ;-) --Daniel PS: Walter: are you going to include this BigInteger class native in phobos soon? I mean that's something that's quite useful for a language to have.
May 27 2004
prev sibling parent reply Stephan Wienczny <wienczny web.de> writes:
Arcane Jill wrote:
 Yes, me.
 
 I'm releasing it next week. It's destined to be called "etc.bigint".
 
 Right now it's still in development. Everything works, but I've got a couple
 more high level functions to add, and a little bit of optimizing and profiling
 to do. Can you wait a week?
 
 What do you need it FOR, by the way? I'll be doing a crypto library next, so if
 you want it for cryptography you could just wait even longer (or collaborate).
 
 Arcane Jill

What kind of algorithms are you planing to implement? Stephan
May 26 2004
parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c93j93$ukc$1 digitaldaemon.com>, Stephan Wienczny says...


What kind of algorithms are you planing to implement?

Stephan

"planning to" impies I haven't done it yet. Should be past tense, in fact. Low level routines are assember optimized. At the higher level, multiplication uses special case algorithms for squaring and multiplication by powers of two, and the Karatsuba-Ofman divide-and-conquer algorithm for very large numbers. Long division uses a radix 2^32 (rather than binary) method. Modulo exponentiation uses Mongomery reduction for odd moduli, and Barrett reduction for even moduli. Factorial and radix convertions do as much work as possible in uints. Modulo inversion uses the fast binary algorithm if the modulus is prime. Primality testing uses a fast lookup table for small numbers, and the Legendre test for larger numbers. (I may also give it a Rabin-Miller test but I haven't done that yet). Square root uses the shift and subtract method (not successive approximation). I may have forgotten to list a few. Other speedups are possible, but I'd say that's pretty ok for a first release. Arcane Jill
May 26 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
Arcane Jill wrote:
 In article <c93j93$ukc$1 digitaldaemon.com>, Stephan Wienczny says...
 
 
 
What kind of algorithms are you planing to implement?

Stephan

"planning to" impies I haven't done it yet. Should be past tense, in fact.

I wanted to know which _crypto_ alogrithm you are going to implement!?! RSA, ECC, Rijndael? Stephan
May 27 2004
parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c94l4e$2fuq$1 digitaldaemon.com>, Stephan Wienczny says...

I wanted to know which _crypto_ alogrithm you are going to implement!?!
RSA, ECC, Rijndael?

Stephan

Woops! Misunderstood you there. Sorry about that. Well, basically all of them. (Not sure I've heard of ECC, but I'm sure I could look it up). In any case, it will be open source, so any I miss out, other people can add. Arcane Jill.
May 27 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
May question was not that clear the first time...
ECC stands for Elliptic Curve Cryptography, maybe you have heard about that.
It's faster then RSA and more secure. It's greatest use today are mobile 
phones and WAP.
If you would like to get some inspiration you could have a look at 
crypto++ (http://sourceforge.net/projects/cryptopp). That's the best C++ 
cryptolib I know.

Stephan

Arcane Jill wrote:
 Woops! Misunderstood you there. Sorry about that.
 
 Well, basically all of them. (Not sure I've heard of ECC, but I'm sure I could
 look it up).
 
 In any case, it will be open source, so any I miss out, other people can add.
 
 Arcane Jill.
 
 

May 27 2004
parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c95pkg$2069$1 digitaldaemon.com>, Stephan Wienczny says...
May question was not that clear the first time...
ECC stands for Elliptic Curve Cryptography, maybe you have heard about that.
... have a look at 
crypto++ (http://sourceforge.net/projects/cryptopp).

Actually, I did know about ECC, and do play to use it - I just hadn't twigged the abbreviation. I knew about crypto++ too. We're off-topic for the thread title here. Feel free to change it if you want to carry on talking about crypto, but my crypto lib is a little way in the future yet. Gotta get those big integers out first. Jill
May 27 2004
parent Hwa Hwa <Hwa_member pathlink.com> writes:
carry on talking about crypto, but my crypto lib is a little way in the future
yet. Gotta get those big integers out first.

Yeah, baby, let's see those big integers of yours. B-)
May 27 2004