#### Archived

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

# 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.

## 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 on other sites
Why don''t you just use a big numbers library, like gmp?

##### Share on other sites
Woot, there exist big number libraries! :D

Thanks!

##### Share on other sites
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 on other sites
well the modulo operator, internally, divides the numbers ^^

##### Share on other sites
Not to mention that you can''t store an integer with "hundreds of decimals" in any ordinary int

##### 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 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 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 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]

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 9
• 15
• ### Forum Statistics

• Total Topics
633392
• Total Posts
3011639
• ### Who's Online (See full list)

There are no registered users currently online

×