square root of a big number

Hi, How to calculate the square root of a big number, for example 2025027714713048816? How to test if a big number is a perfect sqare or not? Thanks

Answer 1

[John D'Errico]

As long as we can start with a uint64 number, this should work reasonably well:

N = uint64(2025027714713048816);

u = uint64(sqrt(double(N)))
u =
           1423034685

Then perform this iteratively, UNTIL u converges:

u = (u + N/u)/2
u =
           1423034685

Wrapping a while loop around it would suffice, but it should not take many iterations. See that the double sqrt has in fact arrived at the proper (approximate) sqrt, with no extra steps required at all.

u*u
ans =
  2025027714713049225

So, not exact, but as close as we can get to the true square root in integers.

vpa(sqrt(sym(N)))
ans =
1423034684.9999998562930319579666

[dedeff]

Hi John D'Errico,

vpa(sqrt(sym(N))) is a perfect solution for my problem.

Thanks

Answer 2

[James Tursa]

You can use the Symbolic Toolbox for this, or use this FEX submission by John D'Errico:

http://www.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-big-decimal-class

Answer 3

[Walter Roberson]

With some tricks you can find the integer portion of the square root of any integer up to 2^64-1 using fzero. Once you have the integer portion, you can square it and compare it to the original value: if they matched then it was a perfect square.

The tricks are not immediately obvious, though. They involve compensating for the fact that a calculation on uint64 cannot go negative, by doing arithmetic on the results of logical tests.

[Sven Stähs]

well this answer would be way more helpful if it actually spelled out what these tricks are instead of giving a vague hint that ther are tricks. "There is a solution, but I'm not telling you what it is, only that it's not obvious". Thanks...