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


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:17