Hoe kan ek optel en aftrek 128 bit heelgetalle in C of C ++ as my samesteller ondersteun dit nie?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianVra
Ek skryf 'n kompressor vir 'n lang stroom van 128 bit nommers. Ek wil graag die getalle op te slaan as verskille -. Berging net die verskil tussen die getalle eerder as die getalle hulself omdat ek die verskille in minder grepe kan pak, want hulle is kleiner
Maar vir kompressie dan moet ek met hierdie 128 bit waardes aftrek, en vir dekompressie ek nodig het om hierdie waardes by te voeg. Maksimum grootte heelgetal vir my samesteller is 64 bisse.
Enigiemand enige idees vir hierdie doeltreffend te doen?
Oplossing
As alles wat jy nodig het, is optel en aftrek, en jy al jou 128-bit waardes in tweeledige vorm, kan 'n biblioteek handig wees, maar is nie streng noodsaaklik. Dit wiskunde is triviale om self te doen.
Ek weet nie wat jou samesteller gebruik vir 64-bit tipes, so ek sal int64 en UINT64 gebruik vir ondertekening en unsigned 64-bis integriteit hoeveelhede.
class Int128
{
public:
...
Int128 operator+(const Int128 & rhs)
{
Int128 sum;
sum.high = high + rhs.high;
sum.low = low + rhs.low;
// check for overflow of low 64 bits, add carry to high
if (sum.low < low)
++sum.high;
return sum;
}
Int128 operator-(const Int128 & rhs)
{
Int128 difference;
difference.high = high - rhs.high;
difference.low = low - rhs.low;
// check for underflow of low 64 bits, subtract carry to high
if (difference.low > low)
--difference.high;
return difference;
}
private:
INT64 high;
UINT64 low;
};
Ander wenke
Neem 'n blik op GMP .
#include <stdio.h>
#include <gmp.h>
int main (int argc, char** argv) {
mpz_t x, y, z;
char *xs, *ys, *zs;
int i;
int base[4] = {2, 8, 10, 16};
/* setting the value of x in base 10 */
mpz_init_set_str(x, "100000000000000000000000000000000", 10);
/* setting the value of y in base 16 */
mpz_init_set_str(y, "FF", 16);
/* just initalizing the result variable */
mpz_init(z);
mpz_sub(z, x, y);
for (i = 0; i < 4; i++) {
xs = mpz_get_str(NULL, base[i], x);
ys = mpz_get_str(NULL, base[i], y);
zs = mpz_get_str(NULL, base[i], z);
/* print all three in base 10 */
printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);
free(xs);
free(ys);
free(zs);
}
return 0;
}
Die produksie is
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Met gestruikel oor hierdie relatief ou post heeltemal deur 'n ongeluk, het ek gedink dit pertinent om uit te brei VoLTE se vorige vermoede ten gunste van onervare lesers.
In die eerste plek, die ondertekende verskeidenheid van 'n 128-bit nommer is -2 127 2 127 -1 en nie -2 127 om 2 127 as oorspronklik bepaal.
In die tweede plek, as gevolg van die sikliese aard van eindige rekenkundige die grootste nodig verskil tussen twee 128-bit getalle is -2 127 2 127 -1, wat 'n stoor voorvereiste van 128-stukkies, nie 129. Hoewel (2 127 -1) - (-2 127 ) = 2 128 -1 wat is duidelik nie groter as ons maksimum 2 127 -1 positiewe heelgetal, rekenkundige oorvloei verseker altyd dat die naaste afstand tussen enige twee n -bit nommers val altyd binne die reeks 0-2 n -1 en dus implisiet -2 n -1 2 n -1 -1.
Om te verduidelik, laat ons eers kyk hoe 'n hipotetiese 3-bit verwerker binêre Daarbenewens sal implementeer. As 'n voorbeeld, kyk na die volgende tabel wat die absolute unsigned verskeidenheid van 'n 3-bis integriteit uitbeeld.
0 = 000 mjd
1 = 001b
2 = 010b
3 = 011b
4 = 100B
5 = 101B
6 = 110B
7 = 111B ---> [Cycles terug na 000 mjd op oorloop]
Uit die bogenoemde tabel is dit geredelik duidelik dat:
001b (1) + 010b (2) = 011b (3)
Dit is ook duidelik dat die byvoeging van enige van hierdie getalle met sy numeriese aanvulling altyd oplewer 2 n -1:
010b (2) + 101B ([aanvulling van 2] = 5) = 111B (7) = (2 3 -1)
As gevolg van die sikliese oorloop wat plaasvind wanneer die toevoeging van twee n -bit getalle resultate in 'n ( n 1) -bit gevolg is, volg dit dus dat die byvoeging enige van hierdie getalle met sy numeriese aanvulling + 1 sal altyd toegee 0:
010b (2) + 110B ([aanvulling van 2] + 1) = 000 mjd (0)
So kan ons sê dat [aanvulling van n ] + 1 = - n , sodat n + [aanvulling van N ] + 1 = n + (- n ) = 0. Verder, as ons weet nou dat n + [aanvulling van n ] + 1 = 0, dan n + [aanvulling van n - x ] + 1 moet = n - ( n - x ). = x
Die toepassing van hierdie ons oorspronklike 3-bit tafel opbrengste:
0 = 000 mjd = [aanvulling van 0] + 1 = 0
1 = 001b = [aanvulling van 7] + 1 = -7
2 = 010b = [aanvulling van 6] + 1 = -6
3 = 011b = [aanvulling van 5] + 1 = -5
4 = 100B = [aanvulling van 4] + 1 = -4
5 = 101B = [aanvulling van 3] + 1 = -3
6 = 110B = [aanvulling van 2] + 1 = -2
7 = 111B = [aanvulling van 1] + 1 = -1 ---> [Cycles terug na 000 mjd op oorloop]
Of die verteenwoordigende onttrekking is positief, negatief of 'n kombinasie van beide as geïmpliseer met onderteken twees-aanvulling rekenkundige, ons het nou 2 n n -bit patrone wat moeiteloos kan dien beide positiewe 0-2 n -1 en negatiewe 0 tot - (2 n ) - 1 reekse soos en wanneer dit nodig is. In punt van die feit, alle moderne verwerkers in diens net so 'n stelsel om te implementeer algemene ALU circuit vir beide optelling en aftrekking bedrywighede. Wanneer 'n CPU ontmoetings 'n i1 - i2 aftrek instruksie, dit intern voer 'n [aanvul + 1] werking op i2 en daarna verwerk die operande deur die toevoeging circuit om te bereken i1 + [aanvulling van i2] + 1. Met die uitsondering van 'n bykomende dra / teken XOR omheinde oorloop vlag, beide onderteken en unsigned Daarbenewens en by implikasie aftrek, is elke implisiete.
As ons die bostaande tabel is van toepassing op die insette volgorde [-2 n -1 , 2 n -1 -1, -2 n -1 ] soos aangebied in oorspronklike antwoord Volte se, ons is nou in staat om saam tempute die volgende N-bit verskille:
diff # 1:
(2 n -1 -1) - (-2 n -1 ) =
3 - (-4) = 3 + 4 =
(-1) = 7 = 111B
diff # 2:
(-2 n -1 ) - (2 n -1 -1) =
(-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b
Begin met ons nageslag -2 n -1 , ons is nou in staat om die oorspronklike insette volgorde weer te gee deur die toepassing van elk van die bogenoemde verskille in volgorde:
(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1
Jy kan natuurlik wil 'n meer filosofiese benadering tot hierdie probleem en die vermoede te neem oor hoekom 2 n siklies-opeenvolgende getalle sou vereis meer as 2 n siklies-opeenvolgende verskille?
Taliadon.
Boost 1.53 sluit nou multiprecision:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
// Requires Boost 1.53 or higher
// build: g++ text.cpp
int main()
{
namespace mp = boost::multiprecision;
mp::uint128_t a = 4294967296;
mp::uint256_t b(0);
mp::uint512_t c(0);
b = a * a;
c = b * b;
std::cout << "c: " << c << "\n";
return 0;
}
Uitgawe:
./a.out
c: 340282366920938463463374607431768211456
Daar is 'n baie literatuur met betrekking tot groot heelgetal wiskunde. Jy kan een van die biblioteke vrylik beskikbaar (sien links) gebruik of jy kan rol jou eie. Alhoewel ek julle gelyk sou waarsku, vir niks meer ingewikkeld as optel en aftrek (en skofte), sal jy nodig het om nie-triviale algoritmes gebruik.
Om optel en aftrek, kan jy 'n klas / struktuur wat twee 64-bit heelgetalle hou skep. Jy kan eenvoudig skool wiskunde gebruik om die optel en aftrek te doen. Basies, doen wat jy doen met 'n potlood en papier te voeg of af te trek, met deeglike oorweging te dra / leen.
Soek vir 'n groot getal. Btw onlangse weergawes van VC ++, IntelC ++ en GCC opstellers het 128-bis integriteit tipes, maar ek is nie seker dit is so maklik toeganklik as wat jy dalk wil (dit bedoel is om gebruik te word met SSE2 / xmms registers).
TomsFastMath is 'n bietjie soos GMP (hierbo genoem), maar is openbare domein, en was ontwerp van die grond af te baie vinnig wees (dit bevat selfs vergadering kode optimalisaties vir x86, x86-64, ARM, SSE2, PPC32, en AVR32).
Ook opmerklik: indien die doel is bloot om die kompressie van 'n stroom van getalle te verbeter deur preprocessing dit, dan die preprocessed stroom nie gemaak moet word van presies rekenkundige verskille. Jy kan XOR (^) gebruik in plaas van + en -. Die voordeel is dat 'n 128-bit XOR is presies dieselfde as twee onafhanklike XORs op die 64-bit dele, so dit is beide eenvoudige en doeltreffende.
