hi. a have a task " Floating point reciprocal square root of integer number without using FP unit. " , and i dont know which algorith should i implement? a have to use MIPS assembly language...
Sounds like this is a piece homework, and that you've been sleeping during class... show a tiny bit of effort yourself?
yeah, its my laboratory task, but i do not ask for code in MIPS, but i ask which algorithm of square root should i take , to be easy to implement in MIPS.. nothing more
Hi, here is an implementation for integer sqarre root using x86_64 assembler, maybe it will help...
.file "math.S"
.text
//
// long new_sqrt( long value );
//
// abstract fast integer square root algorithm.
// Compliant to the x86_64 ABI.
// in rdi = value
// out rax = integer square root of value
//
.align 2
new_sqrt:
pushq %rcx
pushq %rdx
xorq %rax, %rax // c = 0
movq $0x40000000, %rcx // b = 0x40000000
.L1:
cmpq $0, %rcx // b == 0
je .L3 // yes: done
movq %rax, %rdx // t = c
addq %rcx, %rdx // t += b
sarq %rax // c >>= 1
cmpq %rdi, %rdx // r > t
jg .L2 // yes: next
subq %rdx, %rdi // r -= t
addq %rcx, %rax // c += b
.L2:
sarq $2, %rcx // b >>= 2
jmp .L1 // next guess
.L3:
popq %rdx
popq %rcx
ret
.size new_sqrt, . - new_sqrt
.type new_sqrt, @function
.globl new_sqrt
.file "math.S"
.text
//
// long new_sqrt( long value );
//
// abstract fast integer square root algorithm.
// Compliant to the x86_64 ABI.
// in rdi = value
// out rax = integer square root of value
//
.align 2
new_sqrt:
pushq %rcx
pushq %rdx
xorq %rax, %rax // c = 0
movq $0x40000000, %rcx // b = 0x40000000
.L1:
cmpq $0, %rcx // b == 0
je .L3 // yes: done
movq %rax, %rdx // t = c
addq %rcx, %rdx // t += b
sarq %rax // c >>= 1
cmpq %rdi, %rdx // r > t
jg .L2 // yes: next
subq %rdx, %rdi // r -= t
addq %rcx, %rax // c += b
.L2:
sarq $2, %rcx // b >>= 2
jmp .L1 // next guess
.L3:
popq %rdx
popq %rcx
ret
.size new_sqrt, . - new_sqrt
.type new_sqrt, @function
.globl new_sqrt
thanks a lot, but x86 i will have during second half of the semester and do not understand this code at all :(
You can use the property of square sum decomposition: (a+b)^2 = a^2+2ab+b^2.
I only know the algorithm for doing this by hand in a decimal base, but it shouldn't be too hard to implement in software using binary base.
1) split the input number by groups of two digits starting at the decimal point. (e.g. 324 will become 3 and 24, lets call them X and Y. )
2) find a digit, square of which will be less or equal to X. let's call this number Z (=1)
3) subtract it from the X (now X = 2)
4) combine the result with the remaining digit pair Y. (we got 224)
5) do 2Z^2 (=2)
6) find a number which if combined with the result of previous step and multiplied by itself will yield result smaller/equal to the result of 4th step. (in this case it's 8. i.e. 28*8 = 224 => 224 = 224. )
7) repeat the algorithm. (in this example we got a result already, so no need to repeat anything. square root of 324 is 18.)
So in this particular case: a=10*1 and b=8. And indeed: (2*1*10+8)*8=2*1*10*8+8^2 conforms with 2ab+b^2.
I only know the algorithm for doing this by hand in a decimal base, but it shouldn't be too hard to implement in software using binary base.
1) split the input number by groups of two digits starting at the decimal point. (e.g. 324 will become 3 and 24, lets call them X and Y. )
2) find a digit, square of which will be less or equal to X. let's call this number Z (=1)
3) subtract it from the X (now X = 2)
4) combine the result with the remaining digit pair Y. (we got 224)
5) do 2Z^2 (=2)
6) find a number which if combined with the result of previous step and multiplied by itself will yield result smaller/equal to the result of 4th step. (in this case it's 8. i.e. 28*8 = 224 => 224 = 224. )
7) repeat the algorithm. (in this example we got a result already, so no need to repeat anything. square root of 324 is 18.)
So in this particular case: a=10*1 and b=8. And indeed: (2*1*10+8)*8=2*1*10*8+8^2 conforms with 2ab+b^2.
thanks, but i wonder if it is easy to implementi in mips ;/ any other ideas ?