Anonymous user
Isqrt (integer square root) of X: Difference between revisions
Add Rust implementation
(Add Rust implementation) |
|||
Line 2,463:
71: 1,002,260,051,717,656,279,450,068,093,686
73: 7,015,820,362,023,593,956,150,476,655,802
</pre>
=={{header|Rust}}==
<lang rust>
use num::BigUint;
use num::CheckedSub;
use num_traits::{One, Zero};
fn isqrt(number: &BigUint) -> BigUint {
let mut q: BigUint = One::one();
while q <= *number {
q <<= &2;
}
let mut z = number.clone();
let mut result: BigUint = Zero::zero();
while q > One::one() {
q >>= &2;
let t = z.checked_sub(&result).and_then(|diff| diff.checked_sub(&q));
result >>= &1;
if let Some(t) = t {
z = t;
result += &q;
}
}
result
}
fn with_thousand_separator(s: &str) -> String {
let digits: Vec<_> = s.chars().rev().collect();
let chunks: Vec<_> = digits
.chunks(3)
.map(|chunk| chunk.iter().collect::<String>())
.collect();
chunks.join(",").chars().rev().collect::<String>()
}
fn main() {
println!("The integer square roots of integers from 0 to 65 are:");
(0_u32..=65).for_each(|n| print!("{} ", isqrt(&n.into())));
println!("\nThe integer square roots of odd powers of 7 from 7^1 up to 7^74 are:");
(1_u32..75).step_by(2).for_each(|exp| {
println!(
"7^{:>2}={:>83} ISQRT: {:>42} ",
exp,
with_thousand_separator(&BigUint::from(7_u8).pow(exp).to_string()),
with_thousand_separator(&isqrt(&BigUint::from(7_u8).pow(exp)).to_string())
)
});
}
</lang>
{{out}}
<pre>
The integer square roots of integers from 0 to 65 are:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
The integer square roots of odd powers of 7 from 7^1 up to 7^74 are:
7^ 1= 7 ISQRT: 2
7^ 3= 343 ISQRT: 18
7^ 5= 16,807 ISQRT: 129
7^ 7= 823,543 ISQRT: 907
7^ 9= 40,353,607 ISQRT: 6,352
7^11= 1,977,326,743 ISQRT: 44,467
7^13= 96,889,010,407 ISQRT: 311,269
7^15= 4,747,561,509,943 ISQRT: 2,178,889
7^17= 232,630,513,987,207 ISQRT: 15,252,229
7^19= 11,398,895,185,373,143 ISQRT: 106,765,608
7^21= 558,545,864,083,284,007 ISQRT: 747,359,260
7^23= 27,368,747,340,080,916,343 ISQRT: 5,231,514,822
7^25= 1,341,068,619,663,964,900,807 ISQRT: 36,620,603,758
7^27= 65,712,362,363,534,280,139,543 ISQRT: 256,344,226,312
7^29= 3,219,905,755,813,179,726,837,607 ISQRT: 1,794,409,584,184
7^31= 157,775,382,034,845,806,615,042,743 ISQRT: 12,560,867,089,291
7^33= 7,730,993,719,707,444,524,137,094,407 ISQRT: 87,926,069,625,040
7^35= 378,818,692,265,664,781,682,717,625,943 ISQRT: 615,482,487,375,282
7^37= 18,562,115,921,017,574,302,453,163,671,207 ISQRT: 4,308,377,411,626,977
7^39= 909,543,680,129,861,140,820,205,019,889,143 ISQRT: 30,158,641,881,388,842
7^41= 44,567,640,326,363,195,900,190,045,974,568,007 ISQRT: 211,110,493,169,721,897
7^43= 2,183,814,375,991,796,599,109,312,252,753,832,343 ISQRT: 1,477,773,452,188,053,281
7^45= 107,006,904,423,598,033,356,356,300,384,937,784,807 ISQRT: 10,344,414,165,316,372,973
7^47= 5,243,338,316,756,303,634,461,458,718,861,951,455,543 ISQRT: 72,410,899,157,214,610,812
7^49= 256,923,577,521,058,878,088,611,477,224,235,621,321,607 ISQRT: 506,876,294,100,502,275,687
7^51= 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 ISQRT: 3,548,134,058,703,515,929,815
7^53= 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 ISQRT: 24,836,938,410,924,611,508,707
7^55= 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 ISQRT: 173,858,568,876,472,280,560,953
7^57= 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 ISQRT: 1,217,009,982,135,305,963,926,677
7^59= 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 ISQRT: 8,519,069,874,947,141,747,486,745
7^61= 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 ISQRT: 59,633,489,124,629,992,232,407,216
7^63= 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 ISQRT: 417,434,423,872,409,945,626,850,517
7^65= 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 ISQRT: 2,922,040,967,106,869,619,387,953,625
7^67= 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 ISQRT: 20,454,286,769,748,087,335,715,675,381
7^69= 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 ISQRT: 143,180,007,388,236,611,350,009,727,669
7^71= 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 ISQRT: 1,002,260,051,717,656,279,450,068,093,686
7^73= 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 ISQRT: 7,015,820,362,023,593,956,150,476,655,802
</pre>
| |||