It is absolutely crucial to end all of your programs with: return 0; as the last

Question

It is absolutely crucial to end all of your programs with:

return 0;

as the last line before the closing '}' bracket in your main function.
Programs that do not follow this convention will not be graded correctly.
Programs that end with that line may still fail because they do not
generate the right output.


Each sample run is indicated by a line of "=" symbols. These lines only indicate
the start and the end of a sample run and should not be printed by
your program.

Use 64-bit floating point numbers (i.e., double) for all floating point
calculations. Do not use float as your results may differ from the test cases
due to small precision errors.

Problem 5
#########

The integer square root (isqrt) of n is the largest integer that is
less than or equal to the square root of N. One way to compute the
integer square root is to use the Babylonian method.
The Babylonian method is called Babylonian because somebody thought
that Babylonians could use it.

The Babylonian method is an iterative method that starts from some
initial guess x0 and performs the following iteration:

x_next = (x_cur + n/x_cur) / 2

The iteration terminates when the iteration reaches its stable point,
i.e., x_next = x_cur, or when it reaches a cycle, i.e., x becomes
something that occurred before during the iteration. If the cycle ends
with x such that x*x > N, then you need to decrease it until x*x becomes <= N.

The case when N = 0 needs to be handled specially. You need to report
zero iterations in this case and the square root equals zero.

For the initial guess x0 use the number 2^(D/2), where D is an int containing
the number of binary digits (i.e., bits) of the number N.

The first line of the input contains a single number of test cases T,
where 1 <= T <= 10000.

Each of the next T lines contains a number N, where
0 <= N <= 2^64 - 1. For each test case, the program needs to print the
integer square root of N and the number of iterations of the
Babylonian method that it took to compute it.

Hint: The number may not fit in an 'int' or 'double'. You can use a type uint64_t
which is defined in a header file <stdint.h> to represent this number.
Make sure to check the documentation about scanf() to find out how to
read the number properly. One way is to read and print an unsigned 64-bit number
properly is to use the facilities of C99 standard as shown below:

#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>

int main(int argc, const char *argv[]) {
uint64_t int64;
scanf("%" SCNu64, &int64);
printf("%" PRIu64, int64);
system("pause");
return 0;
}

Remarks: Please replicate the exact text of the prompts and the output. Even
though the text must be the same,

============= START OF SAMPLE RUN =======================
---------------- START OF INPUT -------------------------
5
0
1
3
18446744073709551615
1025
----------------- END OF INPUT --------------------------
---------------- START OF OUTPUT ------------------------
0 0
1 1
1 2
4294967295 2
32 1
----------------- END OF OUTPUT -------------------------
============= END OF SAMPLE RUN =======================

Explanation / Answer

Dear Friend hope this will help u out #include #include #include #include uint64_t sqroot(uint64_t &m) { uint64_t i=0; uint64_t x1,x2; while( (i*i)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.