Click here to Skip to main content
15,867,939 members
Articles / Internet of Things / Arduino
Tip/Trick

Integer Square Root on 15 Assembler Lines

Rate me:
Please Sign up or sign in to vote.
5.00/5 (6 votes)
5 Jun 2019CPOL1 min read 18.4K   7   17
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Spain 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.

Comments and Discussions

 
SuggestionA simple port to Visual Studio 2019 Pin
Member 25759447-Jun-19 10:25
Member 25759447-Jun-19 10:25 
GeneralRe: A simple port to Visual Studio 2019 Pin
Southmountain17-Jun-19 18:39
Southmountain17-Jun-19 18:39 
QuestionInteger square root on 15 assembler lines Pin
KerimF6-Jun-19 11:03
KerimF6-Jun-19 11:03 
AnswerRe: Integer square root on 15 assembler lines Pin
altomaltes6-Jun-19 23:05
professionalaltomaltes6-Jun-19 23:05 
GeneralRe: Integer square root on 15 assembler lines Pin
KerimF7-Jun-19 7:58
KerimF7-Jun-19 7:58 
GeneralRe: Integer square root on 15 assembler lines Pin
altomaltes8-Jun-19 9:07
professionalaltomaltes8-Jun-19 9:07 
GeneralRe: Integer square root on 15 assembler lines Pin
DaveBoltman10-Jun-19 2:11
DaveBoltman10-Jun-19 2:11 
PraiseRe: Integer square root on 15 assembler lines Pin
altomaltes10-Jun-19 6:30
professionalaltomaltes10-Jun-19 6:30 
QuestionInteger square root on 15 assembler lines Pin
Frank Malcolm5-Jun-19 22:12
Frank Malcolm5-Jun-19 22:12 
AnswerRe: Integer square root on 15 assembler lines Pin
altomaltes6-Jun-19 6:49
professionalaltomaltes6-Jun-19 6:49 
GeneralRe: Integer square root on 15 assembler lines Pin
Frank Malcolm6-Jun-19 11:04
Frank Malcolm6-Jun-19 11:04 
There are probably not many people who can do long division the old way, let alone square roots. We were taught it in school.
GeneralRe: Integer square root on 15 assembler lines Pin
altomaltes7-Jun-19 1:29
professionalaltomaltes7-Jun-19 1:29 
GeneralRe: Integer square root on 15 assembler lines Pin
KerimF7-Jun-19 3:55
KerimF7-Jun-19 3:55 
GeneralRe: Integer square root on 15 assembler lines Pin
altomaltes8-Jun-19 9:17
professionalaltomaltes8-Jun-19 9:17 
GeneralRe: Integer square root on 15 assembler lines Pin
KerimF9-Jun-19 4:34
KerimF9-Jun-19 4:34 
GeneralRe: Integer square root on 15 assembler lines Pin
Rick York17-Jun-19 13:20
mveRick York17-Jun-19 13:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.