Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
(Add Rust implementation) |
|||
Line 2,463: | Line 2,463: | ||
71: 1,002,260,051,717,656,279,450,068,093,686 |
71: 1,002,260,051,717,656,279,450,068,093,686 |
||
73: 7,015,820,362,023,593,956,150,476,655,802 |
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> |
</pre> |
||