Page 1 of 1
(a) Prove that 1² +2²+ 3² + ... + n² = n(n+1)(2n + 1)/6 (b) We often need to compute x", for large integers n, in many a
Posted: Thu May 05, 2022 1:15 pm
by answerhappygod
- A Prove That 1 2 3 N N N 1 2n 1 6 B We Often Need To Compute X For Large Integers N In Many A 1 (45.28 KiB) Viewed 34 times
(a) Prove that 1² +2²+ 3² + ... + n² = n(n+1)(2n + 1)/6 (b) We often need to compute x", for large integers n, in many applications (e.g., modular arithmetic in cryptography, additive semigroups like elliptic curves, powering of matrices, shortest path computations in large graphs); the simplistic O(n) algorithm of repeated multiplications is slow. Design a logarithmic algorithm (that needs only log n multiplications) for exponentiation where n is a positive integer. You need to prove your claim. (c) Describe (provide pseudocode) Binary Euclid Algorithm to compute the greatest common divisor of two positive integers.