1

I wasn't able to find how gmpxx stores the mpz_t structs under the hood. Thus the only way to get the most significant byte of a number stored as mpz_t is using the mpz_get_str method, but I would expect it to be very slow.

Do you know of a more effective (and simple) way of doing this?

I mean the 'most significant byte' of the number (which is in my case saved as mpz_t) in binary. I.e. for 12345 (10) = 11000000111001 (2) it would be 11000000, no matter gmpxx actually stores it.

SlowerPhoton
  • 888
  • 1
  • 7
  • 17
  • 1
    What's a "_most significant byte_" of a structure? – Ron Nov 03 '17 at 17:29
  • @Ron The MSB is the byte that represents the highest part of a number stored in multiple bytes. The order of these bytes depends on CPU architecture (endianess). – user0042 Nov 03 '17 at 17:32
  • @user0042 that's for a single number. What does MSB mean in the context of a struct? – Kevin Nov 03 '17 at 17:35
  • @Kevin Good point. – user0042 Nov 03 '17 at 17:36
  • Thanks, I clarified it. I don't think the architecture matters. The most significant byte of "123456" is always the same - for big endian the leftmost, for little endian the rightmost, which are equal. – SlowerPhoton Nov 03 '17 at 17:41
  • @Kevin there is no meaning in context of structs in general, but the MSB of `mpz_t` struct would presumably be the the MSB of the most significant *limb* pointed by the struct. – eerorika Nov 03 '17 at 17:45

2 Answers2

1

Two functions to look at here: size_t mpz_sizeinbase(mpz_t op, int base): this returns the length in a base, and for base=2, it gives the number of bits. void mpz_tdiv_r_2exp (mpz_t r, const mpz_t n, mp_bitcnt_t b): this is equivalent to r = n >> b;. Combined, the operation you are looking for is to bit-shift right exactly sizeinbase-8times:

size_t bit_length = mpz_sizeinbase(number, 2);
mpz_tdiv_r_2exp(last_byte, number, bit_length-8);

As a sidenote, the mpz_t struct is stored in "limbs", which are primitives that are chained together. These limbs can have leading 0's to make editing the number easier for small value changes - so accessing them directly is not recommended.

A limb means the part of a multi-precision number that fits in a single machine word. (We chose this word because a limb of the human body is analogous to a digit, only larger, and containing several digits.) Normally a limb is 32 or 64 bits. The C data type for a limb is mp_limb_t. ~https://gmplib.org/manual/Nomenclature-and-Types.html#Nomenclature-and-Types

Kunc
  • 102
  • 2
  • 9
-2

You can create a union without padding (see #pragma pack effect) with 2 members: your struct and a byte, then assign a value to your struct, then read the value of the byte. However, I am not sure if it fits to your definition of MSB.

Andrey Belykh
  • 2,578
  • 4
  • 32
  • 46