Square root

[Thomas_Kuhner]

Does anyone know an algorithm for getting square roots of positive integers? The Math Commands osax is not available for OS X and the shell cannot calculate sqr without additional software like “octave”. - I found Maple code on Wikipedia.org but am stuck with the line

a := r(e);

intsqrt := proc(z) local A,B,a,b,c,e,r;
A := 1;
B:= z;
e := z-1;
while (e>1) do
r := rand(A+1…B-1):
a := r(e);
if (a > A and a^2 < z) then
A := a;
end;
if (a < B and a^2 > z) then
B := a;
end;
e := B-A;
end;
printf(“Integer part of sqrt is %d.\n”, A);
end proc:

intsqrt(9)

on intsqrt(z)
	
	local A, B, _a, _b, c, e, r
	
	set A to 1
	set B to z
	set e to z - 1
	
	repeat while e > 1
		set r to random number from A + 1 to B - 1
		
		-- This has not been translated correctly
		set _a to r -- A :=r(e)
		
		if _a > A and _a ^ 2 < z then
			set A to _a
		end if
		if _a < B and _a ^ 2 > z then
			set B to _a
		end if
		set e to B - A
	end repeat
	return A
	
end intsqrt

Any idea how to translate this line?

TIA!
Thomas

Model: Mac-Mini
Browser: Firefox 1.5.0.3
Operating System: Mac OS X (10.4)

[Bruce_Phillips]

@Thomas Kühner

Any idea how to translate this line?

I’d assume it means: r * e

Edit: It’s possible to do this from the command line (or shell script):

echo 'sqrt (9)' | /usr/bin/bc

[Thomas_Kuhner]

Thanks Bruce!

This was what I was looking for but did not find… hitting “sqr” and pressing “tab” in the terminal did not bring “sqrt” up. Where did you get to know about it from?

echo ‘sqrt (9)’ | /usr/bin/bc

Addendum: got it

man bc

[Qwerty_Denzel]

Can’t you just use ‘to the power of a half’?

on sqrt(aNumber)
	return aNumber ^ 0.5
end sqrt

sqrt(2)
--> 1.414213562373

sqrt(9)
--> 3.0

[Thomas_Kuhner]

That’s absolutely correct! I extended it to intsqrt(aNumber) because I needed the integer part only for calculating primes.

on intsqrt(aNumber)
	
	set aNumber to aNumber ^ 0.5
	
	try
		set aNumber to ((characters 1 thru (offset of "," in (aNumber as string)) of (aNumber as string)) as string) as integer
	end try
	
	log aNumber
	
end intsqrt

[kai]

@Qwerty Denzil

Can’t you just use ‘to the power of a half’?

That’s what I use, Qwerty. Native AppleScript (no external calls), so it’s about 150 times faster here than calling the shell.

Thomas, there’s no need for all the text stuff to get the integer part. Just go for:

on intsqrt(aNumber)
	aNumber ^ 0.5 div 1
end intsqrt

[Adam_Bell]

As integer works too, except that it rounds up when the sqrt gets over x.5

intsqrt(30) → 5
intsqrt(31) → 6

For the purposes of extracting the upper bound of a search for prime numbers, that really doesn’t matter much.

on intsqrt(aNumber)
	aNumber ^ 0.5 as integer
end intsqrt

[kai]

@Adam Bell

As integer works too, except that it rounds up when the sqrt gets over x.5

Besides the rounding up that you mention, there are a couple of other points to bear in mind when comparing as integer with div, Adam:

¢ as just mentioned [url=http://bbs.applescript.net/viewtopic.php?pid=60363#p60363]here[/url], the real-to-integer coercion was only introduced in AppleScript 1.9.2/Mac OS X 10.3

¢ the div function is somewhat faster than the coercion (by a factor of about x3, here)

[Adam_Bell]

Thanks for the test info Kai - I had thought that coercion would be faster without actually testing it. I wonder why Satimage puts “floor” in their mathematical operators given that div 1 produces the same result, and “round realnum rounding down” must be a real dog.

[kai]

Quite. Bit of an unsung hero, is our friend div.

I’d guess that the rounding down parameter was included with the round function purely for completeness. Again, when comparing native AppleScript with an external call (particularly for relatively trivial operations), there’s really no contest. In this case, div is at least 12 times faster than rounding down.

[Nigel_Garvey]

div rounds toward zero, which is down for positives, up for negatives.

[kai]

True, Mr G. I was thinking positive (as ever).