- Forum
- Windows Programming
- How to calculate the square root of a RE
How to calculate the square root of a REALLY BIG NUMBER?
I think the title says it all.. I really need your help.. This is the task I have to solve until my next competition, and I dunno what to do.. I have never solved any of the tasks like this, because I have to work with really, really big numbers.. And to make things even worse, I need to find the square root of a 1000-digit number! I know that no variable is able to handle such a big number so I can: sqrt(the_number) ! I know to code everything except the main part xD It would be really ungrateful to ask you for the solved task, I don't want that.. I just need some help, an idea on how to work with big numbers, and so on.. I think I can read the input and store the data in a char array, so I can classify those characters in a group of two and... what now? xD
--
Mr. Little Z is looking at a piece of paper and unsuccessfully trying to find the square root of a number written on the paper.
Help Mr. Little Z find the number B which is the square root of BIG number A. The number A has 1000 digits at most and the square root of A will always be an integer.
INPUT:
The first line of the standard input contains the number 0<N<=1000, where N is the number of digits in the given number A. The next N lines contain the digits of the number.
OUTPUT:
To the standard output write number M, where M represents the length of number B (where B is the square-root of the number A) and in the next M lines write the digits of the number B (from the most significant digit to the least significant).
Input:
3
6
2
5
Output:
2
2
5
Explanation:
The number written on the paper was 625, and its square-root is 25.
The program must run less than 10 sec, and mustn't use more than 16 MB of memory!
--
Mr. Little Z is looking at a piece of paper and unsuccessfully trying to find the square root of a number written on the paper.
Help Mr. Little Z find the number B which is the square root of BIG number A. The number A has 1000 digits at most and the square root of A will always be an integer.
INPUT:
The first line of the standard input contains the number 0<N<=1000, where N is the number of digits in the given number A. The next N lines contain the digits of the number.
OUTPUT:
To the standard output write number M, where M represents the length of number B (where B is the square-root of the number A) and in the next M lines write the digits of the number B (from the most significant digit to the least significant).
Input:
3
6
2
5
Output:
2
2
5
Explanation:
The number written on the paper was 625, and its square-root is 25.
The program must run less than 10 sec, and mustn't use more than 16 MB of memory!
This reminds me of this http://www.cplusplus.com/forum/lounge/32041/ challenge. Maybe some of those submitted code could help you.
Last edited on
closed account (zvRX92yv)
Get GMP, because the largest standard integer variable is of 64-bit, and it can store an integer of about 18 quintillions.
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
The Babylonian method looks promising.
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
The Babylonian method looks promising.
Last edited on
Maybe you could try creating a class that can hold an infinitely large number? I'm working on an assignment for a class right now to create a class that basically stores the individual characters of a string (like "12389471237894689127346789126348912736489") into a STL list of chars. I just got the addition working so that I can add these "integers" together so I am sure that you could also design a class with a method to compute square root.
@blackcoder41, I cannot access the page, it's not found..
@Nahiyan, that is what I firstly thought about, but the only problem is that I CAN'T use GMP for this task.. all of the work needs to be coded by me, that's some kind of my training for the competition.. The Babylonian method looks promising, but only if I use GMP, right?
@Halo Fan - I agree! That's exactly what do I need to do! But the only question is.. how? :) .... any reference? :D
@Nahiyan, that is what I firstly thought about, but the only problem is that I CAN'T use GMP for this task.. all of the work needs to be coded by me, that's some kind of my training for the competition.. The Babylonian method looks promising, but only if I use GMP, right?
@Halo Fan - I agree! That's exactly what do I need to do! But the only question is.. how? :) .... any reference? :D
This page shows how to find the root digit by digit http://www.wikihow.com/Calculate-a-Square-Root-by-Hand
Topic archived. No new replies allowed.