15,612,351 members
Articles / Internet of Things / Arduino
Tip/Trick
Posted 5 Jun 2019

15.5K views
7 bookmarked

# Integer Square Root on 15 Assembler Lines

Rate me:
This code calculates square root of an integer on a few assembler code lines.

## Introduction

You can use this code on small controllers used on embedded systems, that lacks many arithmetic operations, like Arduino. It calculates the square root stored in BX (31 bit) and puts the result on AL (7 bit) and the remainder on AH (7 bit). It is possible to use the 63/15 bit wide version using the intel extended registers (EBX for input and EAX for results). It is also possible to modify it for arbitrary precision. Only shifts and compare used:

ASM
asm( "mov ax, 0; stc" );            /* Initialize */
asm( "loop:"       );
asm(   "rcl bx, 1; rcl ah, 1"  );
asm(   "shl bx, 1; rcl ah, 1"  );
asm(   "shl al, 2"     );
asm(   "or  al, 1"     );
asm(   "cmp ah, al"    );
asm(   "jc skip"       );
asm(     "sub ah, al"  );
asm(     "or  al,  2"  );

asm( "skip:"           );
asm(   "shr al, 1"     );
asm(   "cmp bx,0x8000" );
asm(   "clc" );
asm(   "jnz  loop"     );

As you can see, it is really tiny and fast.

## Background

While remembering the old long division method for square roots, I thought that the particularities of base 2 binary numeric system could be exploited to simplify this trick, related to "human" base 10 approach.

## Using the Code

The easiest way to test this code is using GCC, as a wrapper:

C++
unsigned char sqrt( unsigned short w )
{ asm( "mov bx, %0 " : "=r" ( w ) );        /* c specifics */

// ------------------------------------> The real code  starts here

asm( "mov ax, 0; stc" );            /* Initialize */
asm( "loop:"       );
asm(   "rcl bx, 1; rcl ah, 1"  );
asm(   "shl bx, 1; rcl ah, 1"  );
asm(   "shl al, 2"     );
asm(   "or  al, 1"     );
asm(   "cmp ah, al"    );
asm(   "jc skip"       );
asm(     "sub ah, al"  );
asm(     "or  al,  2"  );

asm( "skip:"           );
asm(   "shr al, 1"     );
asm(   "cmp bx,0x8000" );
asm(   "clc" );
asm(   "jnz  loop"     );

// ------------------------------------> The real code ends here
}

int main()
{ unsigned short w= sqrt( 25*25+1 );

return( w );
}

You can cut and paste to sqrt.c, add trace points as wished and build it with: gcc.exe -masm=intel sqrt.c

Another option is to use an IDE like codeblocks and trace the execution.

## Points of Interest

This code only uses the source and result registers (BX and AX), so it doesn't "pollute" any other register. It is possible that a quick version exploits the register boundary, but it takes more registers to achieve this. The instruction set used is present in almost all microcontrollers, so porting it is easy.

As an observation, the square root or a binary number takes half of the bits of operand, thus, if operand is 15 bits long, the result can fit on 7 bits (this case), If 31 bits long, fits on 15 bits, and so.

## History

• 5th June, 2019: Initial version

Written By
Software Developer (Senior)
Spain
Involved in tecnology since 18, especially in "low level program". Started with electronics, z80 assembler, i86 assembler, PASCAL, C (microcontrollers), C++. Some awards won in electronic magazines. Some interesting m2m projects. Using and teaching linux since 1995. Degree in electronics.
Creative temperament. This made me well know at work by every folk soon.
Got fun in nature and travelling.

 First Prev Next
 A simple port to Visual Studio 2019 Member 25759447-Jun-19 10:25 Member 2575944 7-Jun-19 10:25
 Re: A simple port to Visual Studio 2019 Southmountain17-Jun-19 18:39 Southmountain 17-Jun-19 18:39
 Integer square root on 15 assembler lines KerimF6-Jun-19 11:03 KerimF 6-Jun-19 11:03
 Re: Integer square root on 15 assembler lines altomaltes6-Jun-19 23:05 altomaltes 6-Jun-19 23:05
 Re: Integer square root on 15 assembler lines KerimF7-Jun-19 7:58 KerimF 7-Jun-19 7:58
 Re: Integer square root on 15 assembler lines altomaltes8-Jun-19 9:07 altomaltes 8-Jun-19 9:07
 Re: Integer square root on 15 assembler lines DaveBoltman10-Jun-19 2:11 DaveBoltman 10-Jun-19 2:11
 Re: Integer square root on 15 assembler lines altomaltes10-Jun-19 6:30 altomaltes 10-Jun-19 6:30
 Integer square root on 15 assembler lines Frank Malcolm5-Jun-19 22:12 Frank Malcolm 5-Jun-19 22:12
 Why are you saying the registers are 7/15/31/63 bits? They're 8, 16, 32 & 64. Thinking of a leading sign bit? Not for a square root. Haven't checked the code, but at a first glance it looks good.
 Re: Integer square root on 15 assembler lines altomaltes6-Jun-19 6:49 altomaltes 6-Jun-19 6:49
 Re: Integer square root on 15 assembler lines Frank Malcolm6-Jun-19 11:04 Frank Malcolm 6-Jun-19 11:04
 Re: Integer square root on 15 assembler lines altomaltes7-Jun-19 1:29 altomaltes 7-Jun-19 1:29
 Re: Integer square root on 15 assembler lines KerimF7-Jun-19 3:55 KerimF 7-Jun-19 3:55
 Re: Integer square root on 15 assembler lines altomaltes8-Jun-19 9:17 altomaltes 8-Jun-19 9:17
 Re: Integer square root on 15 assembler lines KerimF9-Jun-19 4:34 KerimF 9-Jun-19 4:34
 Re: Integer square root on 15 assembler lines Rick York17-Jun-19 13:20 Rick York 17-Jun-19 13:20
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Mar-23 6:06 Refresh 1