A Fun Perfect Square Checker Using Integer Arithmetic Only... ;o)

 
Thread Tools Search this Thread
Operating Systems OS X (Apple) A Fun Perfect Square Checker Using Integer Arithmetic Only... ;o)
# 15  
Old 08-21-2015
Quote:
Originally Posted by sea
Correct me if i'm wrong, but doesnt integer stop at like... 2.7bil?
And if i look at:
Code:
[ 9223372030926249001 -eq 9223372030926249000 ]

And make it easier (for me) to read: 9'223'372'030'926'249'001, which are (rounded up) 10 billion billions, or about 400 times the max of a 'reliable' integer value.
And as on overflow, they stop counting at the ~2.7bils
(overnighted and not used to such high numbers, might be mathematical incorrect proportions, but you get the idea)

One would need (afaik) a long int or int64, which are both (afaik) not available to the bash shell.

hth
So much for getting some sleep...

According to the standards, conforming shells must use signed long int (or something else that provides the same results when working with values in the range of a signed long int). With the bash being talked about on this thread:
Code:
bash-3.2$ getconf LONG_MAX
9223372036854775807
bash-3.2$ test 9223372030926249001 -eq 9223372030926249000
bash-3.2$ echo $?
1
bash-3.2$ test 9223372030926249001 -eq 9223372030926249001
bash-3.2$ echo $?
0
bash-3.2$ test 9223372030926249001 -eq 92233720309262490009
bash: test: 92233720309262490009: integer expression expected
bash-3.2$

shows the results required for a conforming shell in the 1st two examples and shows an allowed (and expected) result for the 3rd case where the last operand is out of the range of a long int (signed or unsigned).

I agree that it is hard to count the digits when looking at numbers that big, but the shell doesn't allow thousands separators in integer constants given to it in expressions nor when they are used as operands for shell built-ins expecting integer arguments.

Last edited by Don Cragun; 08-21-2015 at 01:03 PM.. Reason: Add note about large integer constants in the shell.
This User Gave Thanks to Don Cragun For This Post:
# 16  
Old 08-21-2015
Binary search was a good idea. Needed to watch a few edge cases.

Code:
#!/bin/bash

VAL=${1-100}
MN=1
MX="$((VAL))"
[ "$MX" -ge 3037000499 ] && MX=3037000499 # Square root of highest possible perfect square

function die() {
        local CODE=$1 ; shift
        echo "$@" >&2 ; exit $CODE
}

[ "$VAL" -lt 0 ] && die 1 "Negative numbers not allowed"

while (((MX-MN) > 1 ))
do
        if (( (((MN+MX)/2) * ((MN+MX)/2)) > VAL )) ; then
                MX=$(( (MN+MX) / 2 ))
        elif (( (((MN+MX)/2) * ((MN+MX)/2)) < VAL )) ; then
                MN=$(( (MN+MX) / 2 ))
        else
                break;
        fi
done

(( (((MN+MX)/2) * ((MN+MX)/2)) == VAL )) &&
        die 0 "Square root of $VAL is $(( (MN+MX)/2 ))"

die 1 "$VAL is not a perfect square"

Code:
$ time ./psquare.sh $(( 300000 * 300000 ))
MN=299968, MX=300032
Square root of 90000000000 is 300000

real    0m0.004s
user    0m0.003s
sys     0m0.000s
$


Last edited by Corona688; 08-21-2015 at 01:29 PM..
# 17  
Old 08-21-2015
Quote:
Originally Posted by Don Cragun
So much for getting some sleep...

According to the standards, conforming shells must use signed long int (or something else that provides the same results when working with values in the range of a signed long int).
That is another stroke against bash being standards compliant, then. I recall getting 64-bit numbers on systems where 'long int' is 32 bit (though honestly was quite happy to have them).
# 18  
Old 08-21-2015
Quote:
Originally Posted by Corona688
That is another stroke against bash being standards compliant, then. I recall getting 64-bit numbers on systems where 'long int' is 32 bit (though honestly was quite happy to have them).
If a shell uses signed long long int (64-bits) in an environment where a signed long int is 32-bits, that is still conforming. Any operation using 64-bit ints instead of 32-bit ints will get exactly the same results for any arithmetic operation that does not cause overflow when using 32-bit signed values.
This User Gave Thanks to Don Cragun For This Post:
# 19  
Old 08-21-2015
Hi all...

For those that don't know, ths is the method used...

Take all of the odd numbers in a series:-

1, 3, 5, 7, 9, 11, 13........

Then:-
[1] 1 = 1 = 1^2

[2] 1+3 = 4 = 2^2

[3] 4+5 = 1+3+5 = 9 = 3^2

[4] 9+7 = 1+3+5+7 = 16 = 4^2

[5] 16+9 = 1+3+5+7+9 = 25 = 5^2

[6] 25+11 = 1+3+5+7+9+11 = 36 = 6^2

[7] 36+13 = 1+3+5+7+9+11+13 = 49 = 7^2

And so on...

It is as simple as that, nothing more nothing less...
The linear addition by one of the square bracketed __line_numbers__ are the integer, (perfect), square root...

Hope this makes sense...

As I quoted it is a fun tongue-in-cheek method...
# 20  
Old 08-24-2015
OK. I think I'm caught up on my sleep. And, I think I have a new script that meets all of the requirements (bash script using only integer arithmetic and only using shell built-ins running on Mac OS X on a MacBook Pro (assembled in mid 2014)). I am, however, using OS X version 10.10.5 instead of version 10.7.5 that wisecracker was using.

The bash script wisecracker provided in post #1 in this thread mostly works fine for relatively small values, but takes a LONG time for relatively large values. I was surprised that it said that 0 is not a perfect square instead of saying that the minimum value it would process is 1. I wanted to see what it would do when invoked as:
Code:
perfect_square 1000000002000000001

I wasn't surprised that it came up with the correct answer:
Code:
1000000002000000001 is the perfect square of 1000000001...

but a ps run shortly before it completed showed that it used more than 595 cpu minutes to compute that result.

While that was consuming one core of one cpu, I played around with Corona688's bash script in post #16 in this thread. It correctly reported that 0 is a perfect square (which surprised me since it always uses 1 as the low end of its binary search range). And, due to the way it calculates the stopping point for the binary search and the way it determines the value it is processing, it says:
Code:
9223372030926249001 is not a perfect square

even though the correct response would be:
Code:
Square root of 9223372030926249001 is 3037000499

When given invalid numbers and when given valid numbers that do not fit in a signed long integer, bash prints a diagnostic message when processing that value with Corona688's script and sometimes continues processing and sometimes terminates processing at that point.

I made a slight modification to Corona688's script to read values from a file instead of just processing one command line argument.

And, I produced the following bash script which performs a more traditional binary search. It uses a little bit of number theory to reduce the range of the binary search. (An x-1 or x digit integer, where x is even, will have a square root that is x/2 digits if it has an integer square root.) It performs lots of tests to verify that the input is a valid number and is in range for a signed long int.

It reads its input from a file named file and looks for two values on each line. The 1st value is the number to be processed. The 2nd value (if present) indicates the expected results for the 1st value (-1 if it is not a perfect square or the square root if it is a perfect square). If the expected value does not match the computed value, it prints a diagnostic. If the 2nd value is not present, the result is printed, but not verified.

Code:
#!/bin/bash
# Usage: perfect_square
# Numbers to be processed are read from an input file named file.

# There is no prompting for input.

# The input file format is:
#	number_to_evaluate [expected_result]
# where number_to_evaluate is assumed to be a string of decimal digits with
# an optional leading minus sign, but no leading zeros.  This string will be
# checked to verify that is a positive decimal value <= LONG_MAX and, if it
# is, determine wheter or not it has an integer square root.  If expected
# result is given and is a positive number, it is the square root that is
# expected to be determined from the given number_to_evaluate.  If it is -1,
# number_to_evaluate is not a perfect square.  If expected_result is not
# given, the code will not verify the results computed against the
# expected_value.

# Note that the extensive checks used to verify valid numbers are used
# because the normal -lt, -le, eq, -ne, -ge, and -gt operators are not
# reliable with numbers that overflow a signed long integer.

# The following constants assume a 64-bit signed long int.  If your system
# has a differrent number of bits in a signed long int, these values can be
# determined for your system, respectively, with the command:
#	printf '0k%dpdvp1-d*pq\n' $(getconf LONG_MAX) | dc

# Maximum signed long int
LONG_MAX=9223372036854775807
# Maximum value that can be squared and produce a valid signed long int
MAX_SQUARE_ROOT=3037000499
# (MAX_SQUARE_ROOT - 1) ** 2
MAX_RANGE=9223372024852248004

while read num root
do	# Verify non-empty string, no leading zeros, all digits (other than
	# one allowed leading minus sign)...
	if [[ "$num" = "" ]] || [[ "$num" != "${num##*[![:digit:]-]}" ]] || \
	    [[ "$num" != "${num#[0-]0}" ]] || [[ "$num" != "${num#[0-9-]*-}" ]]
	then	printf '%s %s\n%s: "%s"\n' \
		    'Invalid number (no leading zeros, no non-digits (other' \
		    'than an optional' 'leading -), no empty strings' "$num"
		continue
	fi
	# Verify that 0 <= num <= LONG_MAX...
	if [[ ${#num} -gt ${#LONG_MAX} ]] || \
	    { [[ ${#num} -eq ${#LONG_MAX} ]] && [[ "$num" > "$LONG_MAX" ]];} || \
	    [[ num -lt 1 ]]
	then	printf "Out of range: 0 < x <= $LONG_MAX: x=$num\n"
		continue
	fi
	# Set binary search range...
	if [[ num -gt MAX_RANGE ]]
	then	low=$MAX_SQUARE_ROOT
		high=$MAX_SQUARE_ROOT
	else	# Note that a number containing x or x+1 digits will have a
		# square root that contains x / 2 digits...
		low=$((10 ** ((${#num} - 1) / 2)))
		if [[ ${#num} -eq ${#LONG_MAX} ]]
		then	high=$((MAX_SQUARE_ROOT - 1))
			[[ num -lt high ]] && high=$num
		else	high=$((10 ** ((${#num} - 1) / 2 + 1) - 1))
		fi
	fi
#	printf 'num=%d(%d), root=%s(%d), low=%d(%d), high=%d(%d)\n' \
#	    $num ${#num} "$root" ${#root} $low ${#low} $high ${#high}
	# Search the established range...
	while [[ low -le high ]]
	do	mid=$(((low + high) / 2))
		square=$((mid * mid))
#		printf '\tlow=%d, mid=%d, high=%d, square=%d\n' $low $mid \
#		    $high $square
		if [[ square -eq num ]]
		then	echo "Square root of $num is $mid"
			[[ "$root" != "" ]] && [[ mid -ne root ]] && \
			    echo "*** Expected \"$root\""
			continue 2
		fi
		[[ square -lt num ]] && low=$((mid + 1)) || high=$((mid - 1))
	done
	echo "$num is not a perfect square"
	[[ "$root" != "" ]] && [[ root -ne -1 ]] && echo "*** Expected \"$root\""
done < file

With the following input in file:
Code:
-10000000000000000000000000000 -1
-1 -1
0 0
1 1
2 -1
3 -1
4 2
5 -1
8 -1
9 3
10 -1
1517823 -1
1517824 1232
1517825 -1
1520288 -1
1520289 1233
1520290 -1
1522755 -1
1522756 1234
1522757 -1
1524153208355 -1
1524153208356 1234566
1524153208357 -1
1524155677488 -1
1524155677489 1234567
1524155677490 -1
1524158146623 -1
1524158146624 1234568
1524158146625 -1
9754610360615760 -1
9754610360615761 98765431
9754610360615762 -1
9754610558146623 -1
9754610558146624 98765432
9754610558146625 -1
9754610755677488 -1
9754610755677489 98765433
9754610755677490 -1
1000000002000000000 -1
1000000002000000001 1000000001
1000000002000000002 -1
1000000004000000003 -1
1000000004000000004 1000000002
1000000004000000005 -1
1000000006000000008 -1
1000000006000000009 1000000003
1000000006000000010 -1
9223372024852248003 -1
9223372024852248004 3037000498
9223372024852248005 -1
9223372030926249000 -1
9223372030926249001 3037000499
9223372030926249002 -1
9223372036854775806 -1
9223372036854775807 -1
9223372036854775808 -1
9223372037000249999 -1
9223372037000250000 3037000500
9223372037000250001 -1
9999999999999999999 -1
10000000000000000000000000000 100000000000000
All of the following shold be rejected as invalid numbers (not out of range)...
abcd
001
-01
1-2
-abc
-0

123a
abc-
0-

it produces the output:
Code:
Out of range: 0 < x <= 9223372036854775807: x=-10000000000000000000000000000
Out of range: 0 < x <= 9223372036854775807: x=-1
Out of range: 0 < x <= 9223372036854775807: x=0
Square root of 1 is 1
2 is not a perfect square
3 is not a perfect square
Square root of 4 is 2
5 is not a perfect square
8 is not a perfect square
Square root of 9 is 3
10 is not a perfect square
1517823 is not a perfect square
Square root of 1517824 is 1232
1517825 is not a perfect square
1520288 is not a perfect square
Square root of 1520289 is 1233
1520290 is not a perfect square
1522755 is not a perfect square
Square root of 1522756 is 1234
1522757 is not a perfect square
1524153208355 is not a perfect square
Square root of 1524153208356 is 1234566
1524153208357 is not a perfect square
1524155677488 is not a perfect square
Square root of 1524155677489 is 1234567
1524155677490 is not a perfect square
1524158146623 is not a perfect square
Square root of 1524158146624 is 1234568
1524158146625 is not a perfect square
9754610360615760 is not a perfect square
Square root of 9754610360615761 is 98765431
9754610360615762 is not a perfect square
9754610558146623 is not a perfect square
Square root of 9754610558146624 is 98765432
9754610558146625 is not a perfect square
9754610755677488 is not a perfect square
Square root of 9754610755677489 is 98765433
9754610755677490 is not a perfect square
1000000002000000000 is not a perfect square
Square root of 1000000002000000001 is 1000000001
1000000002000000002 is not a perfect square
1000000004000000003 is not a perfect square
Square root of 1000000004000000004 is 1000000002
1000000004000000005 is not a perfect square
1000000006000000008 is not a perfect square
Square root of 1000000006000000009 is 1000000003
1000000006000000010 is not a perfect square
9223372024852248003 is not a perfect square
Square root of 9223372024852248004 is 3037000498
9223372024852248005 is not a perfect square
9223372030926249000 is not a perfect square
Square root of 9223372030926249001 is 3037000499
9223372030926249002 is not a perfect square
9223372036854775806 is not a perfect square
9223372036854775807 is not a perfect square
Out of range: 0 < x <= 9223372036854775807: x=9223372036854775808
Out of range: 0 < x <= 9223372036854775807: x=9223372037000249999
Out of range: 0 < x <= 9223372036854775807: x=9223372037000250000
Out of range: 0 < x <= 9223372036854775807: x=9223372037000250001
Out of range: 0 < x <= 9223372036854775807: x=9999999999999999999
Out of range: 0 < x <= 9223372036854775807: x=10000000000000000000000000000
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "All"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "abcd"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "001"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "-01"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "1-2"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "-abc"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "-0"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: ""
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "123a"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "abc-"
Invalid number (no leading zeros, no non-digits (other than an optional
leading -), no empty strings: "0-"

with average times:
Code:
real	0m0.042s
user	0m0.037s
sys	0m0.003s

for 10 runs. With the same input file, the modified version of Corona688's script produces the output:
Code:
./Corona: line 14: [: -10000000000000000000000000000: integer expression expected
-10000000000000000000000000000 is not a perfect square
Negative numbers not allowed
Square root of 0 is 0
Square root of 1 is 1
2 is not a perfect square
3 is not a perfect square
Square root of 4 is 2
5 is not a perfect square
8 is not a perfect square
Square root of 9 is 3
10 is not a perfect square
1517823 is not a perfect square
Square root of 1517824 is 1232
1517825 is not a perfect square
1520288 is not a perfect square
Square root of 1520289 is 1233
1520290 is not a perfect square
1522755 is not a perfect square
Square root of 1522756 is 1234
1522757 is not a perfect square
1524153208355 is not a perfect square
Square root of 1524153208356 is 1234566
1524153208357 is not a perfect square
1524155677488 is not a perfect square
Square root of 1524155677489 is 1234567
1524155677490 is not a perfect square
1524158146623 is not a perfect square
Square root of 1524158146624 is 1234568
1524158146625 is not a perfect square
9754610360615760 is not a perfect square
Square root of 9754610360615761 is 98765431
9754610360615762 is not a perfect square
9754610558146623 is not a perfect square
Square root of 9754610558146624 is 98765432
9754610558146625 is not a perfect square
9754610755677488 is not a perfect square
Square root of 9754610755677489 is 98765433
9754610755677490 is not a perfect square
1000000002000000000 is not a perfect square
Square root of 1000000002000000001 is 1000000001
1000000002000000002 is not a perfect square
1000000004000000003 is not a perfect square
Square root of 1000000004000000004 is 1000000002
1000000004000000005 is not a perfect square
1000000006000000008 is not a perfect square
Square root of 1000000006000000009 is 1000000003
1000000006000000010 is not a perfect square
9223372024852248003 is not a perfect square
Square root of 9223372024852248004 is 3037000498
9223372024852248005 is not a perfect square
9223372030926249000 is not a perfect square
9223372030926249001 is not a perfect square
9223372030926249002 is not a perfect square
9223372036854775806 is not a perfect square
9223372036854775807 is not a perfect square
./Corona: line 14: [: 9223372036854775808: integer expression expected
9223372036854775808 is not a perfect square
./Corona: line 14: [: 9223372037000249999: integer expression expected
9223372037000249999 is not a perfect square
./Corona: line 14: [: 9223372037000250000: integer expression expected
9223372037000250000 is not a perfect square
./Corona: line 14: [: 9223372037000250001: integer expression expected
9223372037000250001 is not a perfect square
./Corona: line 14: [: 9999999999999999999: integer expression expected
9999999999999999999 is not a perfect square
./Corona: line 14: [: 10000000000000000000000000000: integer expression expected
10000000000000000000000000000 is not a perfect square
./Corona: line 14: [: abcd: integer expression expected
Square root of abcd is 0
Square root of 001 is 1
Negative numbers not allowed
./Corona: line 14: [: 1-2: integer expression expected
1-2 is not a perfect square
./Corona: line 14: [: -abc: integer expression expected
Square root of -abc is 0
Square root of -0 is 0
./Corona: line 14: [: : integer expression expected
Square root of  is 0
./Corona: line 11: 123a: value too great for base (error token is "123a"

with average times:
Code:
real	0m0.041s
user	0m0.036s
sys	0m0.003s

for 10 runs. Note that it is expected to run faster than the above script because it doesn't perform any error checking and it doesn't process the last two input lines because it dies on any of the last three input lines. I was surprised that the times were so close. (Apparently reducing the binary search range made up for the extra data verification tests.)

Note also that I am not saying that Corona688's script should perform any error checking; that was not a requirement for this project. I machine-generated most of the input file (after I found the anomalies in the results from the ksh script I presented earlier) and added code to verify that the results computed matched known results as a debugging aid.
These 3 Users Gave Thanks to Don Cragun For This Post:
# 21  
Old 08-24-2015
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...
Login or Register to Ask a Question

Previous Thread | Next Thread

8 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Not able to find the perfect code...Geting confused in between

I have to find last delimiter in each line of a file and store the value after the last '/' in a variable in ksh script...Pls Pls help me:(The file is as shown below: /opt/apps/cobqa/apps/abadv/bind/advc0007.bnd /opt/apps/cobqa/apps/abbrio/bind/naac6115.bnd... (5 Replies)
Discussion started by: bhavanabahety
5 Replies

2. Shell Programming and Scripting

egrep line with perfect mach

Hi Input File A L006 AL01 0 (OCK) L006 A006 0 (OCK) L011 AR11 1 (NLOCK) Input File B L006 AL01 0 (OCK) L006 A006 0 (OCK) Need Egrep Command for perfect Match Thanks (4 Replies)
Discussion started by: asavaliya
4 Replies

3. UNIX for Dummies Questions & Answers

Can you perfect my sed ?

I want to print only the lines that meet the criteria : "worde:" and "wordo;" I got this far: sed -n '/\(*\)\1e:\1o;/p;' But it doesn't quite work. Can someone please perfect it and tell me exactly how its a fixed version/what was wrong with mine? Thanks heaps, (1 Reply)
Discussion started by: maximus73
1 Replies

4. Shell Programming and Scripting

how to compare string integer with an integer?

hi, how to I do this? i="4.000" if ; then echo "smaller" fi how do I convert the "4.000" to 4? Thanks! (4 Replies)
Discussion started by: h0ujun
4 Replies

5. Shell Programming and Scripting

Delete text between square brackets and also delete those square brackets using sed or awk

Hi All, I have a text file which looks like this: computer programming systems engineering I want to get rid of these square brackets and also the text that is inside these brackets. So that my final text file looks like this: computer programming systems engineering I am using... (3 Replies)
Discussion started by: shoaibjameel123
3 Replies

6. AIX

I want the perfect user-interface

I've got an aix-box somewhere on the network and a PC on my desk. Nothing fancy so far. The PC is made dual-boot: - windowsXP with putty & winSCP or - slackware 13 with xfce4 installed. The aix-box runs DB2 v8.2 and I've installed db2top to monitor the database. db2top is a character... (0 Replies)
Discussion started by: dr_te_z
0 Replies

7. UNIX for Dummies Questions & Answers

A perfect number shell program

Here's my work of testing whether a number input is perfect or not.. echo Enter a number read no i=1 ans=0 while do if then ans='expr $ans + $i' fi i='expr $i + 1' done if then echo $no is perfect else echo $no is NOT perfect fi (12 Replies)
Discussion started by: Cyansnow
12 Replies

8. Shell Programming and Scripting

extraction of perfect text from file.

Hi All, I have a file of the following format. <?xml version='1.0' encoding='utf-8'?> <tomcat-users> <role rolename="tomcat"/> <role rolename="role1"/> <role rolename="manager"/> <role rolename="admin"/> <user username="tomcat" password="tomcat" roles="tomcat"/> <user... (5 Replies)
Discussion started by: nua7
5 Replies
Login or Register to Ask a Question