Is there a smart way to use large numbers in C++

Question

Since the University is closed and all exams are cancelled due to Corona, I started programming a prime factorization algorithm in C++. Is there a way to use bigger numbers than unsigned long long int? But I must be able to input the number via terminal and calculate with it.

Here is my code so far:

#include <iostream>
#include <bits/stdc++.h>
unsigned long long int number = 1;
int main(int argc, char **argv)
{
    while(1){
        std::cout << "Please enter a number: ";
            unsigned long long int counter = 2;
            unsigned long long int root = 1;
            int err = scanf("%llu",&number);
            if(err != 1){
                number = 1;
                std::cerr << "NOPE" << std::endl;
                return 1;
            }else{
            std::cout << "Prime factors of  " << number << " are: "<<  std::endl;
            if(number < 2){
                number = 1;
                root = 1;
            }else{
                root = sqrt(number);
            }
            while(number != 1){
                // If number % counter == 0, counter must be a prime factor!
                if(number % counter == 0){
                    number = number / counter;
                    root = sqrt(number);
                    std::cout << counter <<  std::endl;
                // If number is smaller than root it must be the last prim factor!  
                }else if(number < root || number < counter){
                    std::cout << number <<  std::endl;
                    break;
                }else{
                    counter++;
                }
            }
        }
    }
    return 0;
}

If you manage to find an algorithm that's better than O(N) then the university will change its name in honour of you. — Bathsheba, Mar 17 '20 at 16:46
Look at the large number library that's part of the Boost distribution. Learning how to use Boost is great for your market value. And it's a steep learning curve. — Bathsheba, Mar 17 '20 at 16:47
Search for the terms "big number," "multiprecision integer," etc. and see what turns up! — templatetypedef, Mar 17 '20 at 16:48
A starting point: https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic — Richard Critten, Mar 17 '20 at 16:48
The right way: get a large integer library which handles arbitrary size numbers. The smart way: python (Special note: I deliberately use python for large scale algorithms or integer math problems, because if performance becomes an issue, I know I'm already on the wrong path. They're all about working smarter, not harder.) — Kenny Ostrom, Mar 17 '20 at 16:50
After some searching I found a good answer for conversion of arbitarty-length decimal strings into binary sequences; after that it's just pretending you have really huge binary registers and implementing add, mult algorithms: https://stackoverflow.com/a/11007021/11547576 — neutrino_logic, Mar 17 '20 at 17:31

score 1 · Answer 1 · edited Mar 17 '20 at 16:56

1

Maybe boost multi-precision library?

edited Mar 17 '20 at 16:56

Ted Lyngmo

93,841
5
60
108

answered Mar 17 '20 at 16:49

Dr. Andrey Belkin

795
1
9
28

3

FYI I almost flagged it as not an answer. In future I recommend to at least explain why you suggest this library. – Dharman Mar 17 '20 at 16:57
3

This upvote is mine. I think the answer is useful (despite it being laconic); the Boost library is excellent. – Bathsheba Mar 17 '20 at 16:59

MikeS159 · Accepted Answer · 2020-03-17T16:58:55.373

1

GMP is a very high performance library for arbitrary precision integer math in C, and it can also be used in C++. There is a string conversion function which will allow you to accept input from the terminal or other string sources.

https://gmplib.org/

Questions on using GMP for prime factorization already exist on Stack Overflow too :)

edited Mar 17 '20 at 16:58

answered Mar 17 '20 at 16:51

MikeS159

1,884
3
29
54

score 0 · Answer 3 · answered Mar 17 '20 at 17:00

Hi if you want to understand and create a good code for doing this stuff you have to study a very important Math topic "Number Theory". A good book could be Kraft,Washington's one. Check it out and study and you will see that thanks base rapresentation and number theory some calculus will be more efficient and easier.

Is there a smart way to use large numbers in C++

3 Answers3