2

So I want to take a logarithm from an int256_t.

I found this but modifying it to take sizeof int256_t did not work. It will give incorrect results: https://stackoverflow.com/a/11376759

Is there a log function in boost which supports multiprecision?

nixygum
  • 21
  • 3
  • 1
    An `int256_t` is just four `int64_t`, and I would expect this built-in to support 64 bits on a 64bit platform. Substitute eight `int32_t`, for a 32bit platform. So this becomes simply a matter of finding the first non-zero `unsigned int`, that comprises the `int256_t`, using `__builtin_clz` on that, and adding the appropriate multiple of 64 or 32 to the result. A little bit more work, but still a piece of cake. – Sam Varshavchik Nov 02 '17 at 12:15
  • @sam plus details; if you have only 1 bit of data in your machine precision value, that may round too much. – Yakk - Adam Nevraumont Nov 02 '17 at 12:22
  • @sam How to do it in C++ code? Maybe I am not getting your point clearly here. Can you formulate in more detail that what should be done to achieve the base 2 logarithm of an int256_t? Thanks for the comment, though. – nixygum Nov 02 '17 at 13:52
  • What exactly don't you "get"? The underlying math, or the C++ code to implement it? If it's the math, I'll be happy to explain. But if you understand the math, the C++ is trivial, and is simply the direct translation of that math, so if you understand the math, but having trouble formulating that into C++ code, then you should simply ask a different question, explaining the math you're trying to calculate, all the code you've managed to write so far, and articulate what's the missing part, or is not working correctly. – Sam Varshavchik Nov 02 '17 at 15:56

2 Answers2

0

Without further constraints I'd write:

Live On Coliru

int256_t x("12345678901234567890");

std::cout << "log2(" << x << ") = " << log2(cpp_bin_float_100(x)) << "\n";

Prints

log2(12345678901234567890) = 63.4206

Simpler

You don't need all that precision if you're going to round the result anyways:

Live On Coliru

std::cout << "log2(" << x << ") = " << log2(x.convert_to<double>()) << "\n";

Ad-hoc

A very crude form could look like:

Live On Coliru

template <typename T>
static inline int adhoc_log2(T i) {
    int n = 0;
    while(i /= 2) ++n;
    return n;
}

Prints

adhoc(12345678901234567890) = 63

Lastly, indeed you could drop back down to bit-level and apply the bit-fiddling hacks in the way @SamVarshavchik suggests

sehe
  • 374,641
  • 47
  • 450
  • 633
0
template<class T, std::size_t...Is>
std::array<uint8_t, bytes> decomponse( std::index_sequence<Is...>, T in ) {
  return {{ (uint8_t)( in >> (8*( (sizeof...(Is)) - Is ) )) }};
}

template<std::size_t bytes, class T>
std::array<int8_t, bytes> decomponse( T in ) {
  return decompose( in, std::make_index_sequence<bytes>{} );
}

template<std::size_t bytes, class T>
double big_log2( T in ) {
  auto bytes_array = decompose<bytes>(in);
  std::size_t zeros = 0;
  for (auto byte:bytes_array) {
    if (byte) break;
    ++zeros;
  }
  int32_t tmp = 0;
  for (auto i = zeros; (i < bytes) && i < (zeros+4); ++i) {
    tmp |= bytes_array[i] << (8*(3 - (i-zeros)));
  }
  return log2(tmp) + (bytes-zeros-4)*8;
}

where log2(int32_t) generates a log2 of a 32 bit value and returns a double.

Depending on endianness, reversing bytes_array and modfying algorithm may make it faster (ideally it should compile down to a memcpy or just be optimized out entirely).

This attempts to shove the 4 highest significance bytes into a int32_t, take its logarithm, then add the right amount to shift it to the magnitude of the N-byte integer in question.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524