Convert big numbers to other base 64

[Won]

Hi everybody!

I'm working on a program and I need to convert big numbers to radix 64.
I would like to shorter them whit conversion that's why I choosed base 64.
I have two problems:

1. The conversion works only for not so big numbers. Untill about 2^32.
I would like to convert bigger numbers. Is there any solution?
(I thought on GMP/MPIR library, but I can't managed it.)

2. The conversion back to decimal base doesn't works, because I use 'strtoul()' which doesn't support bigger bases like 36.
Is there any good method for that?

Thank you!

[JLBorges]

unsigned long long would get you up to 2^64.

If the numbers are larger than that, a large integer type from a library can do the heavy lifting.


> (I thought on GMP/MPIR library, but I can't managed it.)

boost::multiprecision::cpp_int is header-only. And very easy to use.
http://www.cplusplus.com/forum/general/113602/#msg620774

[Won]

I solved it with the GMP library. It's very fast and can handle the huge numbers and shift the base of them too.

Unfortunately I have another problem.

mpz_t value;
mpz_init(value);
mpz_set_ui(value,0);
mpz_set_str(value,inputStr, 10)

The mpz_set_str gives value for the variable. It reads the value what I want to give from a file to inputStr.

The inputStr must be declared like:

char inputStr[1500];

The problem is that my input file can be different size. So I can't set a concret number for elements of array. If I set it to a very big element number I get an error when I run. (with compiling isn't there any problem)
A good alternative would be a vector. I tried it, but I get an error.

Is there any way to use mpz_set_str with a vector? Or any other solution?

Thank you!

[Duthomhas]

STL containers allow direct (pointer) access to the underlying data. So you could use a std::string to hold the text version and pass it to GMP with the .c_str() member function. (Check out the Reference link in the top-right of this page.) Likewise, you can get an array from a std::vector by using the .data() member function.

Just remember, these things are not supposed to be mutable...

Also, you should be able to adjust the size of a number in GMP. I don't remember the function to do it, but... read the docs.

Hope this helps.

[JLBorges]

> mpz_set_str(value,inputStr, 10);
> The mpz_set_str gives value for the variable. It reads the value what I want to give from a file to inputStr.
> The inputStr must be declared like: char inputStr[1500];
> The problem is that my input file can be different size.

Use std::string in conjunction with mpz_set_str() . For instance:

std::string inputStr ;
std::ifstream my_input_file( "my_input_file.txt" ) ;
my_input_file >> inputStr ; // sequence of decimal digits into inputStr

mpz_t value;
mpz_init(value);

mpz_set_str( value, inputStr.c_str() ) ;

[Won]

I'm very helpfull, thank you.

What do you think is there any method to convert numbers to higher bases like 62?

std::string inputStr ;
std::ifstream my_input_file( "my_input_file.txt" ) ;
my_input_file >> inputStr ; // sequence of decimal digits into inputStr

mpz_t value;
mpz_init(value);

mpz_set_str( value, inputStr.c_str() ),10 ;
mpz_out_str(output,62,value);

This code can convert decimal numbers to radix 62. It works betwenn 2-62.
What could I do If I would like to convert it to very high base? For example base 512 or 1024.
What do you thin is it possible? Because If I want to convert it to base 512 I need 512 different character for represent numbers.

[Duthomhas]

Different 'bases' are for humans (so that we can read the numbers).
Once you get up to base 256 then you are using one byte's worth of bits for each 'digit' -- which is the same as saying your number is (1) not human readable and (2) binary storage (because it's an array of bytes).

The GMP stores numbers in arrays of long ints (IIRC), so you could just write that information straight to a binary file.

For so many digits, don't bother to try to use human-readable characters. You would have to start playing with Unicode or Shift-JIS just to do that, which would take more space to keep the number than just the binary data, and humans wouldn't be able to read it anyway.

Hope this helps.

[JLBorges]

> Because If I want to convert it to base 512 I need 512 different character for represent numbers.

In the program, a character is just a number (code point).
Going above base 256 does not really help in reducing the size.

#include <boost/multiprecision/cpp_int.hpp>
#include <string>
#include <deque>
#include <type_traits>
#include <iostream>

template < std::size_t BASE, 
           typename DIGIT = typename std::conditional< BASE <= ( std::numeric_limits<unsigned char>::max() + 1 ), unsigned char, std::uint16_t >::type > 
std::deque<DIGIT> to_base( const std::string& unsigned_decimal )
{
    static_assert( BASE > 1 && BASE <= ( std::numeric_limits<DIGIT>::max() + 1 ), "" ) ;
    std::deque<DIGIT> result ;
    
    boost::multiprecision::cpp_int number(unsigned_decimal) ;
    while( number != 0 ) 
    {
        // std::cout << number << '\n' ;
        const boost::multiprecision::cpp_int digit = number % BASE ;
        result.push_front( digit.convert_to<DIGIT>() ) ;
        number /= BASE ;
    }
    
    std::cout << std::dec << "\n\n" << result.size() << " digits to base " << BASE << " == " 
              << result.size() * sizeof(DIGIT) << " bytes\n" ;
    return result ;
}

int main()
{
    const std::string number =  "1234565789012345657890123456578901234565789012345657890123456578901234565789012345657890"
                                "1234565789012345657890123456578901234565789012345657890123456578901234565789012345657890" 
                                "1234565789012345657890123456578901234565789012345657890123456578901234565789012345657890" 
                                "1234565789012345657890123456578901234565789012345657890123456578901234565789012345657890" 
                                "1234565789012345657890123456578901234565789012345657890123456578901234565789012345657890" ;
                                
    for( auto code_point : to_base<64>(number)  ) std::cout << std::hex << int(code_point) << ' ' ;
    for( auto code_point : to_base<256>(number)  ) std::cout << std::hex << int(code_point) << ' ' ;
    for( auto code_point : to_base<65536>(number)  ) std::cout << std::hex << int(code_point) << ' ' ;
}

g++ -std=c++11 -Wall -Wextra -pedantic-errors -O2 main.cpp && ./a.out
244 digits to base 64 == 244 bytes
22 28 29 d 37 3b 39 d 1d ...

183 digits to base 256 == 183 bytes
6 31 2f e2 b8 50 0 7a fc 98 76 ...

92 digits to base 65536 == 184 bytes
6 312f e2b8 5000 7afc 9876 ...

http://coliru.stacked-crooked.com/a/a8c89e17b5efd0b8

[Won]

Hm, I don't know.
I use base 62 at the moment.
The input number is decimal and 4194304 digit long! In base 62 it is just 2340060 digit (4096 kb and 2286 kb).

[JLBorges]

If the reduction in size is for storage/transmission, just compress the number as plain text.

libbzip2 is non-viral and compresses text very well. http://bzip.org/

[Won]

I have one more question.
I have the input in a text file. I read it from it to a string. How can I read only the first n character to the string?

Thank you.

[JLBorges]

#include <iostream>
#include <fstream>
#include <iomanip>

int main()
{
    std::ifstream file(__FILE__) ;
    std::string str ;
    char c ;

    // read characters (including whitespace) up to a delimiter
    std::getline( file, str, '&' ) ;
    std::cout << str << "\n\n" ;

    // skip leading white space, read a maximum of 15 characters or till a whitespace
    file >> std::setw(15) >> str ;
    std::cout << str << "\n\n" ;

    // do not skip leading white space, read a maximum of 25 characters (including whitespace) or eof
    str.clear() ;
    while( str.size() < 25 && file.get(c) )  str += c ;
    std::cout << str << "\n\n" ;

    // read a maximum of 30 characters (excluding whitespace) or eof
    str.clear() ;
    while( str.size() < 30 && file >> c )  str += c ;
    std::cout << str << "\n\n" ;
}

[Won]

Thank you very much! :)