1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/internal/charconv_bigint.h"
16
17 #include <string>
18
19 #include "gtest/gtest.h"
20
21 namespace absl {
22 ABSL_NAMESPACE_BEGIN
23 namespace strings_internal {
24
TEST(BigUnsigned,ShiftLeft)25 TEST(BigUnsigned, ShiftLeft) {
26 {
27 // Check that 3 * 2**100 is calculated correctly
28 BigUnsigned<4> num(3u);
29 num.ShiftLeft(100);
30 EXPECT_EQ(num, BigUnsigned<4>("3802951800684688204490109616128"));
31 }
32 {
33 // Test that overflow is truncated properly.
34 // 15 is 4 bits long, and BigUnsigned<4> is a 128-bit bigint.
35 // Shifting left by 125 bits should truncate off the high bit, so that
36 // 15 << 125 == 7 << 125
37 // after truncation.
38 BigUnsigned<4> a(15u);
39 BigUnsigned<4> b(7u);
40 BigUnsigned<4> c(3u);
41 a.ShiftLeft(125);
42 b.ShiftLeft(125);
43 c.ShiftLeft(125);
44 EXPECT_EQ(a, b);
45 EXPECT_NE(a, c);
46 }
47 {
48 // Same test, larger bigint:
49 BigUnsigned<84> a(15u);
50 BigUnsigned<84> b(7u);
51 BigUnsigned<84> c(3u);
52 a.ShiftLeft(84 * 32 - 3);
53 b.ShiftLeft(84 * 32 - 3);
54 c.ShiftLeft(84 * 32 - 3);
55 EXPECT_EQ(a, b);
56 EXPECT_NE(a, c);
57 }
58 {
59 // Check that incrementally shifting has the same result as doing it all at
60 // once (attempting to capture corner cases.)
61 const std::string seed = "1234567890123456789012345678901234567890";
62 BigUnsigned<84> a(seed);
63 for (int i = 1; i <= 84 * 32; ++i) {
64 a.ShiftLeft(1);
65 BigUnsigned<84> b(seed);
66 b.ShiftLeft(i);
67 EXPECT_EQ(a, b);
68 }
69 // And we should have fully rotated all bits off by now:
70 EXPECT_EQ(a, BigUnsigned<84>(0u));
71 }
72 }
73
TEST(BigUnsigned,MultiplyByUint32)74 TEST(BigUnsigned, MultiplyByUint32) {
75 const BigUnsigned<84> factorial_100(
76 "933262154439441526816992388562667004907159682643816214685929638952175999"
77 "932299156089414639761565182862536979208272237582511852109168640000000000"
78 "00000000000000");
79 BigUnsigned<84> a(1u);
80 for (uint32_t i = 1; i <= 100; ++i) {
81 a.MultiplyBy(i);
82 }
83 EXPECT_EQ(a, BigUnsigned<84>(factorial_100));
84 }
85
TEST(BigUnsigned,MultiplyByBigUnsigned)86 TEST(BigUnsigned, MultiplyByBigUnsigned) {
87 {
88 // Put the terms of factorial_200 into two bigints, and multiply them
89 // together.
90 const BigUnsigned<84> factorial_200(
91 "7886578673647905035523632139321850622951359776871732632947425332443594"
92 "4996340334292030428401198462390417721213891963883025764279024263710506"
93 "1926624952829931113462857270763317237396988943922445621451664240254033"
94 "2918641312274282948532775242424075739032403212574055795686602260319041"
95 "7032406235170085879617892222278962370389737472000000000000000000000000"
96 "0000000000000000000000000");
97 BigUnsigned<84> evens(1u);
98 BigUnsigned<84> odds(1u);
99 for (uint32_t i = 1; i < 200; i += 2) {
100 odds.MultiplyBy(i);
101 evens.MultiplyBy(i + 1);
102 }
103 evens.MultiplyBy(odds);
104 EXPECT_EQ(evens, factorial_200);
105 }
106 {
107 // Multiply various powers of 10 together.
108 for (int a = 0 ; a < 700; a += 25) {
109 SCOPED_TRACE(a);
110 BigUnsigned<84> a_value("3" + std::string(a, '0'));
111 for (int b = 0; b < (700 - a); b += 25) {
112 SCOPED_TRACE(b);
113 BigUnsigned<84> b_value("2" + std::string(b, '0'));
114 BigUnsigned<84> expected_product("6" + std::string(a + b, '0'));
115 b_value.MultiplyBy(a_value);
116 EXPECT_EQ(b_value, expected_product);
117 }
118 }
119 }
120 }
121
TEST(BigUnsigned,MultiplyByOverflow)122 TEST(BigUnsigned, MultiplyByOverflow) {
123 {
124 // Check that multiplcation overflow predictably truncates.
125
126 // A big int with all bits on.
127 BigUnsigned<4> all_bits_on("340282366920938463463374607431768211455");
128 // Modulo 2**128, this is equal to -1. Therefore the square of this,
129 // modulo 2**128, should be 1.
130 all_bits_on.MultiplyBy(all_bits_on);
131 EXPECT_EQ(all_bits_on, BigUnsigned<4>(1u));
132 }
133 {
134 // Try multiplying a large bigint by 2**50, and compare the result to
135 // shifting.
136 BigUnsigned<4> value_1("12345678901234567890123456789012345678");
137 BigUnsigned<4> value_2("12345678901234567890123456789012345678");
138 BigUnsigned<4> two_to_fiftieth(1u);
139 two_to_fiftieth.ShiftLeft(50);
140
141 value_1.ShiftLeft(50);
142 value_2.MultiplyBy(two_to_fiftieth);
143 EXPECT_EQ(value_1, value_2);
144 }
145 }
146
TEST(BigUnsigned,FiveToTheNth)147 TEST(BigUnsigned, FiveToTheNth) {
148 {
149 // Sanity check that MultiplyByFiveToTheNth gives consistent answers, up to
150 // and including overflow.
151 for (int i = 0; i < 1160; ++i) {
152 SCOPED_TRACE(i);
153 BigUnsigned<84> value_1(123u);
154 BigUnsigned<84> value_2(123u);
155 value_1.MultiplyByFiveToTheNth(i);
156 for (int j = 0; j < i; j++) {
157 value_2.MultiplyBy(5u);
158 }
159 EXPECT_EQ(value_1, value_2);
160 }
161 }
162 {
163 // Check that the faster, table-lookup-based static method returns the same
164 // result that multiplying in-place would return, up to and including
165 // overflow.
166 for (int i = 0; i < 1160; ++i) {
167 SCOPED_TRACE(i);
168 BigUnsigned<84> value_1(1u);
169 value_1.MultiplyByFiveToTheNth(i);
170 BigUnsigned<84> value_2 = BigUnsigned<84>::FiveToTheNth(i);
171 EXPECT_EQ(value_1, value_2);
172 }
173 }
174 }
175
TEST(BigUnsigned,TenToTheNth)176 TEST(BigUnsigned, TenToTheNth) {
177 {
178 // Sanity check MultiplyByTenToTheNth.
179 for (int i = 0; i < 800; ++i) {
180 SCOPED_TRACE(i);
181 BigUnsigned<84> value_1(123u);
182 BigUnsigned<84> value_2(123u);
183 value_1.MultiplyByTenToTheNth(i);
184 for (int j = 0; j < i; j++) {
185 value_2.MultiplyBy(10u);
186 }
187 EXPECT_EQ(value_1, value_2);
188 }
189 }
190 {
191 // Alternate testing approach, taking advantage of the decimal parser.
192 for (int i = 0; i < 200; ++i) {
193 SCOPED_TRACE(i);
194 BigUnsigned<84> value_1(135u);
195 value_1.MultiplyByTenToTheNth(i);
196 BigUnsigned<84> value_2("135" + std::string(i, '0'));
197 EXPECT_EQ(value_1, value_2);
198 }
199 }
200 }
201
202
203 } // namespace strings_internal
204 ABSL_NAMESPACE_END
205 } // namespace absl
206