Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Boops

Dividing really big integers

This topic is 5279 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'd like to try some things like finding factors of really big integers (like integers with hundreds of decimals), but I don't really have a clue how to begin. I think I'll represent the integers with an array of decimals (I'll work decimal instead of binary I think, speed isn't really my biggest problem atm), but how could one check if such a thing is divisible through some other big integer? Do you really have to do the division, or is there a faster way to see if it's divisible, without actually dividing? Thanks! [edited by - Boops on June 2, 2004 10:15:01 AM]

Share this post


Link to post
Share on other sites
Advertisement
quote:
Original post by Boops
how could one check if such a thing is divisible through some other big integer? Do you really have to do the division, or is there a faster way to see if it''s divisible, without actually dividing?



int i, j;
if (i%j == 0)
{
// i/j gives a whole number
}


not sure if there is a faster way but you said u didn''t care about speed.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
well the modulo operator, internally, divides the numbers ^^

Share this post


Link to post
Share on other sites
IIRC the machine code integer division returns both the divided integer and the carry. But that isn''t really relevant to ''Big Integers''

You could sift out some of the basic division stuffs... an odd number isn''t divisable by even number and so forth. It should cut down on a large amount of work, but that would only help if speed was an issue.

Share this post


Link to post
Share on other sites
Yeah I implemented a program like that awhile ago. It takes an array (up to 32768 elements long), where each element holds a digit 0-32767, and each element number is that number * 32768^(element number). It was decent, but division got messy and the division kind of froze my computer past about 50 factorial / 2 (my division algorithm really really stunk)

[edited by - uber_n00b on June 3, 2004 6:54:44 PM]

Share this post


Link to post
Share on other sites
Could we keep on substracting until one number is less than the other number?
It will be trivial to implement. You just need to keep a counter and you get both quotient and remainder by subtraction.
Just an idea.

Share this post


Link to post
Share on other sites
quote:
Original post by Peter19852001
Could we keep on substracting until one number is less than the other number?

It will be trivial to implement. You just need to keep a counter and you get both quotient and remainder by subtraction.
Just an idea.


Yes if you want to wait until the end of the universe Big numbers are big ! Big numbers to me range from 2^128 2^512.

Factorizing big number is an ultimately complex problem in math both practically and theorically. A lot of high level research is done around this subject.

Boops I can only advise you to learn the basics first, the Euclidian division algo. And then Google for the tons ofmath ressources on the web. Once you understand Euclide, you'll have to cope with infinitely more complex stuff.

Else if you numbers are not that big, yes there are several free libraries to do that.



[edited by - Charles B on June 5, 2004 6:07:24 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!