OS X (Apple)

Not too related, but i use this check for int or floating point in ksh93

Code:

# We need KSH93 for this, for ksh88 we will need to replace the second case with proper syntax which is a bit larger and more complex.
function checkint {
case "${1}" in
        +([0-9]))
        printf "%s \n" "Int check OK with input ${1}"
        return 0
;;
        +([0-9]).{1,3}([0-9]))
        printf "%s \n" "Floating point upto 3 decimals check OK with input ${1}"
        return 0
;;
        *)
        printf "%s \n" "Int check failed with input ${1}"
        return 1
;;
esac
}

Actually you haven't. It is perfectly OK to have discussions and exhibit different opinions. It is also perfectly OK to expose factual errors in the reasoning of others. (Who would know that better than me who has been - rightfully - corrected over and over again here, most oftenly by Don Cragun.)

I think that, even restricting yourself to integer arithmetic and built-ins, you could speed up the process by using better algorithms. For instance, an application of Newtons method of caluclating the roots of differentiable functions (also called "Netwon-Raphson-method):

Suppose some real function f: [a,b] -> R, which is differentiable everywhere on the intervall [a,b] with values only in R.

It can easily be shown that, starting from an initial guess x[n] (as long as x[n] is reasonably close to x), a better guess x[n+1] can be calculated using the formula

Code:

                   f( x  )
                       n
    x     = x  - -------------
      n+1    n     f'( x  )
                        n

by solving for the tangents equation at f(x)=y and then solving for the x-intercept of this line (Simpsons approximation).

Applying this to get the zeroes of the iteration function f(x) = x**2 - a brings us to the "babylonian method" or "Heron's method" of calculating roots:

Because of the deriative f'(x) = 2x for the solution sqrt(a) we get the approximation

Code:

                    2                 
                   x  - a            
                    n         1          a  
   x     := x  - --------- = --- ( x  + ---- )
     n+1     n    2 x         2     n    x
                     n                    n

by which we calculate a series of xi's (i=0,1,2,...), which will converge against x, until a sufficient approximation is reached.

kshs floats are double-precision, as described at KSH-93 - The KornShell Command and Programming Language:
I hope this helps.

bakunin

Hi bakunin...

i wrote a version of Newton's method using ASIC for MS-DOS years ago as the 'SQRT' command/function did not exist in its compiler. It was accurate enough after 10 iterations.

https://en.wikipedia.org/wiki/ASIC_programming_language

But I really enjoy forced restriction and non-standard solutions to a problem.

My bash version requires no knowledge of serious maths whatsoever and uses an observation that is little known to the general public...

I wasn't really interested in speed just the unusualness, (is there such a word?), of the idea to see how easy it was in integer only bash scripting...

I suspect there might be an upper limit to this method but I don't know what the various shells upper arithmetic limits are, I am assuming 2^31 for 32s bit and 2^63 for 64 bits for positive numbers.

Not sure how one would apply the other formula(e) to bash's integer integer arithmetic without the use of either awk and or bc/dc...

Finally I was aware of the general accuracy of the floating point maths but not sure how for example '1/3' would be interpreted:-

Code:

Last login: Fri Aug 21 12:50:02 on console
AMIGA:barrywalker~> ksh
AMIGA:uw> x=$((1/3))   
AMIGA:uw> echo $x
0
AMIGA:uw> x=$((1.0/3.0))
AMIGA:uw> echo $x 
0.333333333333333333
AMIGA:uw> echo $(($x*3.0))
0.999999999999999999
AMIGA:uw> _

You see my point as echo $((int($x*3.0))) would round down to 0, zero...

You mean that sqares of consecutive natural numbers have the property x[i+1]**2 - x[i]**2 = 2x[i]+1 = 2x[i+1]-1?

OK, here is a short integer implementation, which comes "from top", not "from bottom" (meaning the guesses are always higher than the real value and dropping to it).

Code:

#! /bin/bash

pNextGuess ()
{
     typeset -i iLastGuess=$1
     typeset -i iSquare=$2
     typeset -i iNextGuess=$(( ( iLastGuess + iSquare / iLastGuess ) / 2 ))

     echo $iNextGuess

     return 0
}

# main ()
typeset -i iSquare=$1
typeset -i iGuess=1
typeset -i iNextGuess=0

while : ; do
     iNextGuess=$(pNextGuess $iGuess $iSquare)
     if [ $iNextGuess -eq $iGuess ] ; then
          if [ $(( iGuess * iGuess )) -eq $iSquare ] ; then
               echo "Solution is $iGuess"
          else
               echo "no perfect square, best approximation is $iGuess"
          fi
          exit 0
     fi
     iGuess=iNextGuess
done

A small problem, though: some values cause the guesses to oszillate between two values because of the integers: 960 (961 would be 31**2) is such a number, for instance, because the final guesses will be 30, 31, 30, 31, 30, ....

I (don't think this helps anyone, but) hope this increases the fun.

bakunin

Hi wisecracker,
In my defense, you originally stated:
I see that you said that you used bash (twice), but I don't see any requirement that alternative proposals should use bash nor that they should only use shell built-ins. The INTEGER specification was in the title, but not in the text of the message. I missed that point, so I admit that I did cheat.

Moving on to your later question:
I provided a similar degree of INPUT error correction with added checking to avoid rounding errors that could arise from processing floating point input values such as:

Code:

perfect_square 1.44
1.44 is the perfect square of 1.19999999999999996...

With your bash script using 64-bit signed integer arithmetic, I would expect that the largest square your script could process would be:

Code:

perfect_square 9223372030926249001
9223372030926249001 is the perfect square of 3037000499...

(i.e., the largest perfect square <= 9223372036854775807 [2**63 - 1]). With ksh93 and awk there could be some issues due to floating point artifacts with operands greater than 15 digits when performing floating point operations (only square root calculation in this script uses floating point arithmetic), but since the check at the end was using integer arithmetic, I thought the test should still be valid. But, going back and checking what was going on, I seem to have found a bug in the ksh test -eq operator on OS X (version sh (AT&T Research) 93u+ 2012-08-01). When testing integer numeric values that fit in a long int (64-bit signed int on OS X), the command:

Code:

[ $square -eq $number ]

should be performing an integer test for comparison. But, I found that the commands:

Code:

[ 9223372030926249001 -eq 9223372030926249000 ]
               and
[ 9223372030926249001 -eq 9223372030926249002 ]

both evaluate to true (which means it must be testing those values with a floating point comparison that has lost low end details due to the number of significant digits).

And I realized that the way I was testing could give false negatives when using int(xxx.9999xxx) would truncate to an integer when I needed to round to an integer. (I see other people have also commented on this while I was debugging my code last night and this morning.)

So, coding around my bug and the ksh bug, the following modified script should give you correct results for any value for which your original version would give correct results (and the runtime is not noticeably different from my earlier version):

Code:

#!/bin/ksh
# perfect_square <number>
number=$1
if [ "$number" -eq "$((int(number)))" ] > /dev/null 2>&1 
then
	if [ "$number" -lt 0 ]
	then
		echo "Warning! Integer is negative!!!"
		echo "Set input integer to the DEMO value of 99..."
		number=99
	fi
else
	echo "Invalid Argument! Set input integer to the DEMO value of 100..."
	number=100
fi
root=$((int(sqrt(number) + .5))) # Fix my bug...
square=$((root * root))
if [ $square = $number ] # "=" not "-eq" to avoid ksh bug
then
	echo "$number is the perfect square of $root..."
	exit 0
else
	echo "Integer $number is not a perfect square..."
	exit 1
fi

With the .5 added to the int() argument, that takes care of my bug. Note that square=$((root * root)) may yield a floating point value if and only if the result overflows a signed long int. And, if that happen, there will be a decimal point in the result. This will cause the script to report that the result is not a square even if it happens to be a square (such as with 100000000000000000000), but that cannot happen for any 63 bit integer value that it a perfect square that could be processed by your bash script. I should add a test at the start to check for input larger than LONG_MAX, but I'm not going to try to do that (when I can't trust the test -gt operator) until I get some sleep.

Please read all of the above carefully. It has been a while since I put in an all-nighter to track down a coding bug... It is now 7:20am and I'm going to bed.

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

BASH has had 64 bit integers for ages now. Really ancient versions (pre-3.x) won't have it, though, and this only refers to BASH, not Bourne shells in general.