Prev: LPc2478 external Sdram initialization Help Needed
Next: atmega48 adc at faster than best clock speeds
From: Datesfat Chicks on 4 Feb 2010 21:26
"Nobody" <nobody(a)nowhere.com> wrote in message
news:pan.2010.02.05.01.38.49.156000(a)nowhere.com...
> On Thu, 04 Feb 2010 14:22:54 -0500, Datesfat Chicks wrote:
>
>> I have the need in a microcontroller application to calculate
>> floor(sqrt(x))
>> where x is approximately in the range of 2^32 - 2^64.
>>
>> What are the algorithms I should look at?
>
> Newton-Raphson or bisection, depending upon how slow division is. N-R is
> asymptotically faster (the number of correct digits doubles at each step),
> but each step requires a division.
>
> Bisection is essentially your option b), but it can be computed much more
> efficiently than the algorithm given. You don't need arbitrary multiplies,
> only shifts, as:
>
> (a+2^k)^2 = a^2 + 2.a.2^k + (2^k)^2
> = a^2 + a.2^(k+1) + 2^2k

The identity you provided above is so obvious that I'm beating myself on the
head with a hammer right now for not spotting that as an alternative to
multiplying again on each iteration.

Ouch ouch ouch.

Thanks sincerely.

As you know, division of large integers is fairly expensive on a little
microcontroller. The "bisection" insight you provided is definitely
something I will investigate.

Datesfat

From: Datesfat Chicks on 7 Feb 2010 00:23
"Steve C" <smallpond(a)juno.com> wrote in message
news:hki8bg$ors$1(a)news.eternal-september.org...
>
> ISTR that there was a proof that N-R converged for 32-bit numbers
> to the correct 16-bit result given this starting value in at most
> 3 iterations, but I no longer have the analysis. At any rate,
> it would not be difficult to test.

One thing I often do is simulate microcontroller algorithms on a PC. I
would find out rather rapidly for the 2^32 case whether it always converged
within three iterations. I don't know how long it would take, but
definitely under an hour and probably much less.

However, some of the integers I'm interested in may be around 2^64. I
believe that would be a problem even for a PC. So some formal analysis
would be necessary.

Datesfat

From: Enrico on 7 Feb 2010 01:26
On Feb 4, 12:22 pm, "Datesfat Chicks" <datesfat.chi...(a)gmail.com>
wrote:
> Hi,
>
> I have the need in a microcontroller application to calculate floor(sqrt(x))
> where x is approximately in the range of 2^32 - 2^64.
>
> What are the algorithms I should look at?
>
> These small microcontrollers are characterized by having a 8-bit times 8-bit
> to give 16-bit result integer unsigned multiply instruction, and a similar
> 16/8 division instruction to give a quotient and a remainder.
> Mulitplications of larger integers have to be done by multiplying the bytes
> and adding.
>
> I'm aware of these algorithms:
>
> a)Adding consecutive odd integers and counting how many you have to add,
> i.e. 1 + 3 = 4, 4 + 5 = 9, 9 + 7 = 16, 16 + 9 = 25, etc.
>
> b)Trial squaring, testing setting each bit to "1", i.e.
>
> http://www.uculib.com/vvcuculib01/viewvc.cgi/uculib01/src/stm8/cosmic...
>
> c)Another method that seems to work (don't know the name of it), here is
> source code:
>
> http://www.uculib.com/vvcuculib01/viewvc.cgi/uculib01/src/stm8/cosmic...
>
> What other options should I investigate?
>
> Thanks, Datesfat

=========================================================

From this site:

http://www.convict.lu/Jeunes/Math/square_root_CORDIC.htm

(Copied from site, untested)
Here a C-routine for integer-square-rooting for numbers between 0 and
65536:

int sqrt (int x)
{
int base, i, y ;
base = 128 ;
y = 0 ;
for (i = 1; i <= 8; i++)
{
y + = base ;
if ( (y * y) > x )
{
y -= base ; // base should not have been
added, so we substract again
}
base >> 1 ; // shift 1 digit to the right = divide
by 2
}
return y ;
}


Enrico
From: vinnie on 16 Feb 2010 16:35
Is this a homework question?

You might want to consider a 32 bit MCU with Floating Point Unit.
http://america.renesas.com/fmwk.jsp?cnt=r32c111_root.jsp&fp=/products/mpumcu/m16c_family/r32c100_series/r32c111_group/


--Vinnie

---------------------------------------
Posted through http://www.EmbeddedRelated.com
First  |  Prev  | 
Pages: 1 2
Prev: LPc2478 external Sdram initialization Help Needed
Next: atmega48 adc at faster than best clock speeds