Repository navigation
Expand file tree
/
Copy pathexample006_gcd.cpp
More file actions
193 lines (142 loc) · 22.9 KB
/
Copy pathexample006_gcd.cpp
File metadata and controls
193 lines (142 loc) · 22.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
///////////////////////////////////////////////////////////////////
// Copyright Christopher Kormanyos 2018 - 2026. //
// Distributed under the Boost Software License, //
// Version 1.0. (See accompanying file LICENSE_1_0.txt //
// or copy at http://www.boost.org/LICENSE_1_0.txt) //
///////////////////////////////////////////////////////////////////
#include <examples/example_uintwide_t.h>
#include <math/wide_integer/uintwide_t.h>
namespace local_gcd
{
auto example006_gcd_part_01() -> bool;
auto example006_gcd_part_02() -> bool;
auto example006_gcd_part_01() -> bool // LCOV_EXCL_LINE
{
#if defined(WIDE_INTEGER_NAMESPACE)
using local_wide_integer_type = WIDE_INTEGER_NAMESPACE::math::wide_integer::uint256_t;
#else
using local_wide_integer_type = ::math::wide_integer::uint256_t;
#endif
auto result_is_ok = true;
{
constexpr auto a = local_wide_integer_type("0x1035452A5197CF882B5B5EB64C8CCFEE4D772F9F7B66A239649A43093464EFF5");
constexpr auto b = local_wide_integer_type("0xB4F6151D727361113083D9A0DEB91B0B62A250F65DA6543823703D0140C873AD");
constexpr auto c = gcd(a, b);
constexpr auto result_gcd_is_ok = (static_cast<std::uint32_t>(c) == static_cast<std::uint32_t>(UINT32_C(11759761)));
static_assert(result_gcd_is_ok, "Error: example006_gcd not OK!");
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
{
constexpr auto a = local_wide_integer_type("0xD2690CD26CD57A3C443993851A70D3B62F841573668DF7B229508371A0AEDE7F");
constexpr auto b = local_wide_integer_type("0xFE719235CD0B1A314D4CA6940AEDC38BDF8E9484E68CE814EDAA17D87B0B4CC8");
constexpr auto c = gcd(a, b);
constexpr auto result_gcd_is_ok = (static_cast<std::uint32_t>(c) == static_cast<std::uint32_t>(UINT32_C(12170749)));
static_assert(result_gcd_is_ok, "Error: example006_gcd not OK!");
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
{
constexpr auto a = local_wide_integer_type("0x7495AFF66DCB1085DC4CC294ECCBB1B455F65765DD4E9735564FDD80A05168A");
constexpr auto b = local_wide_integer_type("0x7A0543EF0705942D09962172ED5038814AE6EDF8EED2FC6C52CF317D253BC81F");
constexpr auto c = gcd(a, b);
// This is a lucky random catch here, since the number 13,520,497 is also a prime number.
constexpr auto result_gcd_is_ok = (static_cast<std::uint32_t>(c) == static_cast<std::uint32_t>(UINT32_C(13520497)));
static_assert(result_gcd_is_ok, "Error: example006_gcd not OK!");
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
return result_is_ok; // LCOV_EXCL_LINE
}
auto example006_gcd_part_02() -> bool
{
#if defined(WIDE_INTEGER_NAMESPACE)
using local_wide_integer_type =
WIDE_INTEGER_NAMESPACE::math::wide_integer::uintwide_t
<WIDE_INTEGER_NAMESPACE::math::wide_integer::size_t { UINT16_C(3648) },
WIDE_INTEGER_NAMESPACE::math::wide_integer::uint_defaultlimb_t,
std::allocator<WIDE_INTEGER_NAMESPACE::math::wide_integer::uint_defaultlimb_t>>;
#else
using local_wide_integer_type =
::math::wide_integer::uintwide_t
<::math::wide_integer::size_t { UINT16_C(3648) },
::math::wide_integer::uint_defaultlimb_t,
std::allocator<::math::wide_integer::uint_defaultlimb_t>>;
#endif
auto result_is_ok = true;
{
// Here is a ten decimal digit GCD-result obtained from arguments
// to the gcd() function having approximately 1,000 decimal digits.
// The result 1'072'266'061 is not prime, but nearly prime.
// Its prime factorization is given by:
// FactorInteger[1072266061] = {{3671, 1}, {292091, 1}}
// a_max: 179495542716617411282288837281288720342150328972243065510326237844171305307002799922644842226393826981934287011422087671120024178833792280236249115213708352224874577127657710654845654857847824113375295021430585557360277062099946634436178174734145332464124733002820658550251351150422909857144326296158406242541591423025358444907727464610378373042242850296662470887782620890905312810058006826787178558703791331852252431943226258998686491144641238358668413478648804266589075560289084333650673005047007699095759126408530703527907215186662089057811673884792694865137849750020766363222077779852771746021957763143405214169845835312059943836261558443833291091826628966710144999410449129530036494319738899044257822399858345745963488767426137302563013140016669670229314306589712652704572858446157448228175729337060131188308445884082120280694794476392347934645841056171353341735286796609626555599325115635719793869913637420830008135345972481403822186637531529565890420529485133924817483862663693126363592037153015885057899261479644962318536615839408881
// b_max: 180901493413383064725932686786456334030897287442458223972800037477908820627782812757754695766511221119137415476043600208901194966943320339567571393909946196832630097150670909809840228494254348717729713542114487280515961705559983141587753225416234658076652930011227927067350127533993041833231561696629859873558951562897119929046342517698692135684105822728917948924703577494349323188180220372383849004606043568764473279596966055236400861340879714723785830599947793322186065084787576330145132373599793711521036712336324882960935409928379954884815317968150044760860727739130890275442290729780464669429186757773261213186330749412692264658593239469019564615289747504894185415863708999295661285030828251782659851813005529837497141088585838498177593909872803317400745322369137736194058718737970033470026288021369123605771676495340806021663764437328173386306559539647400296632739725650133174683055197794588601763229044495171946360047562913720518558276982012164919176482094423647411535185149561877125869886503505382638129998164090134575742150262331788
// c_max: 1072266061
const auto a = local_wide_integer_type("179495542716617411282288837281288720342150328972243065510326237844171305307002799922644842226393826981934287011422087671120024178833792280236249115213708352224874577127657710654845654857847824113375295021430585557360277062099946634436178174734145332464124733002820658550251351150422909857144326296158406242541591423025358444907727464610378373042242850296662470887782620890905312810058006826787178558703791331852252431943226258998686491144641238358668413478648804266589075560289084333650673005047007699095759126408530703527907215186662089057811673884792694865137849750020766363222077779852771746021957763143405214169845835312059943836261558443833291091826628966710144999410449129530036494319738899044257822399858345745963488767426137302563013140016669670229314306589712652704572858446157448228175729337060131188308445884082120280694794476392347934645841056171353341735286796609626555599325115635719793869913637420830008135345972481403822186637531529565890420529485133924817483862663693126363592037153015885057899261479644962318536615839408881");
const auto b = local_wide_integer_type("180901493413383064725932686786456334030897287442458223972800037477908820627782812757754695766511221119137415476043600208901194966943320339567571393909946196832630097150670909809840228494254348717729713542114487280515961705559983141587753225416234658076652930011227927067350127533993041833231561696629859873558951562897119929046342517698692135684105822728917948924703577494349323188180220372383849004606043568764473279596966055236400861340879714723785830599947793322186065084787576330145132373599793711521036712336324882960935409928379954884815317968150044760860727739130890275442290729780464669429186757773261213186330749412692264658593239469019564615289747504894185415863708999295661285030828251782659851813005529837497141088585838498177593909872803317400745322369137736194058718737970033470026288021369123605771676495340806021663764437328173386306559539647400296632739725650133174683055197794588601763229044495171946360047562913720518558276982012164919176482094423647411535185149561877125869886503505382638129998164090134575742150262331788");
const auto c0 = gcd(a, b);
const auto c1 = gcd(b, a);
const auto result_gcd_is_ok = (c0 == static_cast<std::uint32_t>(UINT32_C(1'072'266'061)))
&& (c1 == static_cast<std::uint32_t>(UINT32_C(1'072'266'061)));
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
{
// a_max: 2705025496357527397844950019343351415832253793585524919208477198016037659239728714139453742745092178501359870046477483420291547494135409721451503117753322572826878248314276656380423246063009928201989224232542516302250819719103420894850126655950391237995542392724998928912993510811237164714535257372945543809145100521524575091791672825582068130368517314881431770683486345615567601565161194749474278095224855764621700523982113337669344330993455935294013675649386069346972623199236868280951070884063000131892407099693096859249530879596744983473672539507283435684144268287695194474953487659133567326765399617640440195701655972897305760402537322840119799287140872840671390995686811361264738444753647862719325624770517305564619551131205075330873551215858538001671553299998641182798359672871249041915348521624804911306129940087119190009370961301492252346457754080694924586526379387943871581688735112292299607374376862494735300422227394412790934545049156916847198512219640799681023050971733462297096772536218326875007563935607570369986637697963381249262803886805900475
// b_max: 197053799198276552393386327398862312491417217649108631362636583609597487998909781076830916075219694686407032217845862562830932277244316262389233074472150557354656400794049199578919258666819275112938467106339290413303561080431675990291988622227874867334936394336732309305558287215640220273087209084696140383306916932927651634331189908208508339403883178804154919604735519792762259386873402562186195501832515482445185617652954318713216632043671414695855784116646253589428084826969624004537857650426075825691714689156681710398367502079138933887289893554734481497228242864161744866979864303947726055139112870382285437766855272636235079955982699018291892057825081778286094355159985794855613550964711602542070494311070268407840783883428773695889559107058992116942999264004998178012603921615802545312252231101957589287877901606841489761725059234533658544309338810236431224538122765163541141495634971930698285527871463497672845940210989979239888320148468072016928976576446859962954229443394724745365554729665716220677997946496899784251249794444715835
// c_max: 768805905
const auto a = local_wide_integer_type("2705025496357527397844950019343351415832253793585524919208477198016037659239728714139453742745092178501359870046477483420291547494135409721451503117753322572826878248314276656380423246063009928201989224232542516302250819719103420894850126655950391237995542392724998928912993510811237164714535257372945543809145100521524575091791672825582068130368517314881431770683486345615567601565161194749474278095224855764621700523982113337669344330993455935294013675649386069346972623199236868280951070884063000131892407099693096859249530879596744983473672539507283435684144268287695194474953487659133567326765399617640440195701655972897305760402537322840119799287140872840671390995686811361264738444753647862719325624770517305564619551131205075330873551215858538001671553299998641182798359672871249041915348521624804911306129940087119190009370961301492252346457754080694924586526379387943871581688735112292299607374376862494735300422227394412790934545049156916847198512219640799681023050971733462297096772536218326875007563935607570369986637697963381249262803886805900475");
const auto b = local_wide_integer_type("197053799198276552393386327398862312491417217649108631362636583609597487998909781076830916075219694686407032217845862562830932277244316262389233074472150557354656400794049199578919258666819275112938467106339290413303561080431675990291988622227874867334936394336732309305558287215640220273087209084696140383306916932927651634331189908208508339403883178804154919604735519792762259386873402562186195501832515482445185617652954318713216632043671414695855784116646253589428084826969624004537857650426075825691714689156681710398367502079138933887289893554734481497228242864161744866979864303947726055139112870382285437766855272636235079955982699018291892057825081778286094355159985794855613550964711602542070494311070268407840783883428773695889559107058992116942999264004998178012603921615802545312252231101957589287877901606841489761725059234533658544309338810236431224538122765163541141495634971930698285527871463497672845940210989979239888320148468072016928976576446859962954229443394724745365554729665716220677997946496899784251249794444715835");
const auto c0 = gcd(a, b);
const auto c1 = gcd(b, a);
const auto result_gcd_is_ok = (c0 == static_cast<std::uint32_t>(UINT32_C(768'805'905)))
&& (c1 == static_cast<std::uint32_t>(UINT32_C(768'805'905)));
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
{
// a_max: 2970913358969351643808911062351262224442984768999889412380326077579629331833719313112408642903381829181846757367250790177373127600768136970307576484615936521709834003821392562558675651009156628816077956141515143053560094021679575597858688965194475727620376521071784245482749752072196825900341752677337628241036893505373425315252662214279999985272773715317034966158655354727053638985990961277608745118222195499331167545896097039702361191670137927014538848893783140744864088438303321912240860804642910185953216997066232206220194989232836071363764073385965006862541525640538495279547863405618345018894896447864926592768896846541285775303487062553244233562505342342757912335440030040140983477676709986681532110351332112337738787867921832585199164027120327040356845413799404241005715514559131060493319855861186857015761008161802155101895448134736183765439895921986912287450375928009729739252445497274074718717863980179829045291520595655976173871492582538330498966482421542742996673037332548414251932396666712160580667760768325377056959743640650412965587644376759712
// b_max: 3798799310066428980393406895643452224777738389224033620811559098695821626071802098787746580143296049865992766957359814198391034965961345859484253603002429450326722255786939460853049563472855707892691651038014767226097469942194312818046020569336245561967660960011549595500089248648022688560708893039038386043761228664231035730554614501332103765451188149152080016843620463458842602242815761537058493969542657271300696838124314292037100727100530813649756589375144810172927051617221636153446317931577520490622361062062032428245213056215258823336081619623868856623425953573536081967715163775785983894774540895913255505561634088567107619546600299959937223332551289675853934439325509354249819513125691772480124080478908903233171969713594175936882570074391626475321644856139388388603711782385897591037850738482362408119050664710168811752869862630515353488944003673973548941265474658010838492124524051268540864362330537420387680008589276449719898222935524697631641052708206999649116744164401014739540886773058654279117011740755472978076131409273932733064403459031854418
// c_max: 238233486
const auto a = local_wide_integer_type("2970913358969351643808911062351262224442984768999889412380326077579629331833719313112408642903381829181846757367250790177373127600768136970307576484615936521709834003821392562558675651009156628816077956141515143053560094021679575597858688965194475727620376521071784245482749752072196825900341752677337628241036893505373425315252662214279999985272773715317034966158655354727053638985990961277608745118222195499331167545896097039702361191670137927014538848893783140744864088438303321912240860804642910185953216997066232206220194989232836071363764073385965006862541525640538495279547863405618345018894896447864926592768896846541285775303487062553244233562505342342757912335440030040140983477676709986681532110351332112337738787867921832585199164027120327040356845413799404241005715514559131060493319855861186857015761008161802155101895448134736183765439895921986912287450375928009729739252445497274074718717863980179829045291520595655976173871492582538330498966482421542742996673037332548414251932396666712160580667760768325377056959743640650412965587644376759712");
const auto b = local_wide_integer_type("3798799310066428980393406895643452224777738389224033620811559098695821626071802098787746580143296049865992766957359814198391034965961345859484253603002429450326722255786939460853049563472855707892691651038014767226097469942194312818046020569336245561967660960011549595500089248648022688560708893039038386043761228664231035730554614501332103765451188149152080016843620463458842602242815761537058493969542657271300696838124314292037100727100530813649756589375144810172927051617221636153446317931577520490622361062062032428245213056215258823336081619623868856623425953573536081967715163775785983894774540895913255505561634088567107619546600299959937223332551289675853934439325509354249819513125691772480124080478908903233171969713594175936882570074391626475321644856139388388603711782385897591037850738482362408119050664710168811752869862630515353488944003673973548941265474658010838492124524051268540864362330537420387680008589276449719898222935524697631641052708206999649116744164401014739540886773058654279117011740755472978076131409273932733064403459031854418");
const auto c0 = gcd(a, b);
const auto c1 = gcd(b, a);
const auto result_gcd_is_ok = (c0 == static_cast<std::uint32_t>(UINT32_C(238'233'486)))
&& (c1 == static_cast<std::uint32_t>(UINT32_C(238'233'486)));
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
{
// a_max: 4055640284991320004332280601284761394181260289830124026733189144145338999498128868554026214690486750115461278216906289905632757820729042963946509696032705732239185158346748989497228964803063308675343446206234986307059511805414786613900895088905749272967207833766495403598321414073463603250334518597918915032245255233771579002338025675704166720431128820161446451859361898020092163058877921364280179098513205559701097563143562263026757821654882952410684485122289771968121337897242428707545656609394655898931346345549971250120743906371841065560418341716056644364805836542875535993873578424288148467462987156327498257731128154871281843956059548981244325952037029098344251926208210343695193329885474416845827703335141799594458684553484344510647401100527585821556728090663057562963937852163107473225691992042101695817087224818731255553864787137856700951757479073325163730427678909996449954301757899693423515830676827270347298630540005693080162359166994970889064690718079660709521929666249269047308324969480463011979750301291231202500834866228111509224791889399862399
// b_max: 77503666153799051266764042152649962195860378484513205957048174597513407360270276800632488561489348668863014767633003344689266580399988934023022115356771235672885573383328671998563519513630179836853823748382938931899980716031279258062955749384476290694562448821148397946728344923516593829978608487475583881886833650680111650871264147780204537004531708686592566180842842305984854305299296545931978730267009920776974181381330387572769672549278450870357599327589778843138944742439544755666155533508051597484681253885258460549443378396629098717745955795754096176169526813128551756096093318442541451867468597620301632522734916824124956489147138029688273809909363679666343397372151696741012573726556899616306946624876982437086313644523351273580861400658611207850108309300565515328081720864365594843941559946604489658529981443149295746920284697676021743861555440134776689028297178834373907364746667718624703158292584687164669132426968818411195688006839301287416054215563566424843726642105431437658466284774974031854274245091666276472177895683830551283097712551197838480011895455801630283
// c_max: 192152913
const auto a = local_wide_integer_type("4055640284991320004332280601284761394181260289830124026733189144145338999498128868554026214690486750115461278216906289905632757820729042963946509696032705732239185158346748989497228964803063308675343446206234986307059511805414786613900895088905749272967207833766495403598321414073463603250334518597918915032245255233771579002338025675704166720431128820161446451859361898020092163058877921364280179098513205559701097563143562263026757821654882952410684485122289771968121337897242428707545656609394655898931346345549971250120743906371841065560418341716056644364805836542875535993873578424288148467462987156327498257731128154871281843956059548981244325952037029098344251926208210343695193329885474416845827703335141799594458684553484344510647401100527585821556728090663057562963937852163107473225691992042101695817087224818731255553864787137856700951757479073325163730427678909996449954301757899693423515830676827270347298630540005693080162359166994970889064690718079660709521929666249269047308324969480463011979750301291231202500834866228111509224791889399862399");
const auto b = local_wide_integer_type("77503666153799051266764042152649962195860378484513205957048174597513407360270276800632488561489348668863014767633003344689266580399988934023022115356771235672885573383328671998563519513630179836853823748382938931899980716031279258062955749384476290694562448821148397946728344923516593829978608487475583881886833650680111650871264147780204537004531708686592566180842842305984854305299296545931978730267009920776974181381330387572769672549278450870357599327589778843138944742439544755666155533508051597484681253885258460549443378396629098717745955795754096176169526813128551756096093318442541451867468597620301632522734916824124956489147138029688273809909363679666343397372151696741012573726556899616306946624876982437086313644523351273580861400658611207850108309300565515328081720864365594843941559946604489658529981443149295746920284697676021743861555440134776689028297178834373907364746667718624703158292584687164669132426968818411195688006839301287416054215563566424843726642105431437658466284774974031854274245091666276472177895683830551283097712551197838480011895455801630283");
const auto c0 = gcd(a, b);
const auto c1 = gcd(b, a);
const auto result_gcd_is_ok = (c0 == static_cast<std::uint32_t>(UINT32_C(192'152'913)))
&& (c1 == static_cast<std::uint32_t>(UINT32_C(192'152'913)));
result_is_ok = (result_gcd_is_ok && result_is_ok);
}
return result_is_ok;
}
} // namespace local_gcd
#if defined(WIDE_INTEGER_NAMESPACE)
auto WIDE_INTEGER_NAMESPACE::math::wide_integer::example006_gcd() -> bool
#else
auto ::math::wide_integer::example006_gcd() -> bool
#endif
{
return (local_gcd::example006_gcd_part_01() && local_gcd::example006_gcd_part_02());
}
// Enable this if you would like to activate this main() as a standalone example.
#if defined(WIDE_INTEGER_STANDALONE_EXAMPLE006_GCD)
#include <iomanip>
#include <iostream>
auto main() -> int
{
#if defined(WIDE_INTEGER_NAMESPACE)
const auto result_is_ok = WIDE_INTEGER_NAMESPACE::math::wide_integer::example006_gcd();
#else
const auto result_is_ok = ::math::wide_integer::example006_gcd();
#endif
std::cout << "result_is_ok: " << std::boolalpha << result_is_ok << std::endl;
return (result_is_ok ? 0 : -1);
}
#endif