Hi Don...
Phew, that took some reading...
As 0^2 is 0, I never even considered it to be a perfect square so I stand corrected.
My error; however my code can very easily be changed to cater for it.
As you say it is slow, but it was coded from an observation not from any mathematical set of algorithms, that is, every _line_no_ is the perfect square of the odd number series...
Yes, it was a long post. I hope a few people found the narrative informative.
My code rejected 0 since your code didn't process it correctly. If you'd like to modify my script to accept 0, here is a diff showing the changes needed:
48,49c48,49
< [[ num -lt 1 ]]
< then printf "Out of range: 0 < x <= $LONG_MAX: x=$num\n"
---
> [[ num -lt 0 ]]
> then printf "Out of range: 0 <= x <= $LONG_MAX: x=$num\n"
58c58
< low=$((10 ** ((${#num} - 1) / 2)))
---
> low=$((10 ** ((${#num} - 1) / 2) - 1))
Your code used the observation that the sum of all of the odd numbers from 0 to x is a perfect square. My code used the observation that the square root of any positive x digit number has a square root between 10^((x-1)/2) and 10^(((x-1)/2)+1)-1 inclusive (except for the number 0 [since 10^0 is 1; not 0]).
Your code starts with the lowest perfect square and calculates successive perfect squares until it has a perfect square that is greater than or equal to the number being checked. My code performs a binary search of the possible square roots that could match the target number until it determines that there is a square root in range that is the square root of the target or determines that one does not exist.
For a 63-bit integer value, your code may need to loop through millions of possible perfect squares. A binary search like my code uses needs to loop through no more than 32 possible square roots. My code needs less than that since it restricts the high and low possible square roots based on the number of digits in the target number.
OK, here is another take at finding the square root: it does not use any operation other than subtraction/addition and it is no approximation method.
The math is simple: we know that
2 2 2
( a + b ) = a + 2ab + b
or, in the special case of b = 1 :
2 2
( n + 1 ) = n + 2n + 1
which we can more conveniently write as:
2 2
( n + 1 ) = n + n + ( n + 1 ))
This means that
n
--- 2
\ 2i + 1 = n
/__
i=0
In less mathematical terms: we have two counters, x and y. We start with x=0, y=1 and we add them both to a sum, incrementing the counters at each pass. Here is a little table:
Pass x y sum
1 0 1 1
2 1 2 4
3 2 3 9
4 3 4 16
As you can see the "y"-column always holds the root to the square in the "sum"-column.
To find the root i simply reversed that and subtracted (instead of added) from the value originally given down to 0. The code is very simple:
#! /bin/bash
typeset -i iInput=$1
typeset -i iCnt1=0
typeset -i iCnt2=1
while [ $iInput -gt 0 ] ; do
(( iInput = iInput - iCnt1 ))
if [ $iInput -lt $iCnt2 ] ; then
echo "Not a perfect square."
exit 0
fi
(( iInput = iInput - iCnt2 ))
(( iCnt1++ ))
(( iCnt2++ ))
done
echo Solution: $iCnt1
exit 0
bakunin
Hi,
For fun in bash:
#!/bin/bash
XX=$1
YY=$((${#XX}&1 ? 1 : 2))
ZZ=${XX:0:$YY}
AA=$(((${#XX}-YY)/2))
VV=${XX:$YY:$((AA*2))}
BB=0
DD=1
EE=1
while (($EE))
do
ZZ=$((ZZ-DD))
BB=$((ZZ>=0 ? BB+1 : BB))
DD=$((ZZ>=0 ? DD+2 : DD-2))
EE=$((ZZ>=0 ? 1 : 0))
ZZ=$((ZZ>=0 ? ZZ : ZZ+DD+2))
done
rac=$rac$BB
II=0
while (($AA))
do
BB=0
EE=1
DD=$((((DD+1)*10)+1))
ZZ=$((ZZ*100))
UU=${VV:$II:1}
UU=$((UU*10))
UU=$((UU+${VV:II+1:1}))
ZZ=$((ZZ+UU))
while (($EE))
do
ZZ=$((ZZ-DD))
BB=$((ZZ>=0 ? BB+1 : BB))
DD=$((ZZ>=0 ? DD+2 : DD-2))
EE=$((ZZ>=0 ? 1 : 0))
ZZ=$((ZZ>=0 ? ZZ : ZZ+DD+2))
done
rac=$rac$BB
II=$((II+2))
AA=$((AA-1))
done
(( ! ZZ )) && echo $XX is perfect square of $rac || echo $XX is not a perfect square
Examples:
$ ./p_square.sh 391362529049165025
391362529049165025 is perfect square of 625589745
$ ./p_square.sh 98743978937000250000
98743978937000250000 is perfect square of 9937000500
$ ./p_square.sh 98743978937000250011
98743978937000250011 is not a perfect square