Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Assembly code for sin(x) using Taylor expansion

In x86 Linux, how can I implement sin(x) in assembly code using Taylor Expansion?

like image 217
Hamid Avatar asked Aug 10 '09 02:08

Hamid


People also ask

What is the Taylor series expansion of Sinx?

From Taylor's theorem: sinx=N∑n=0f(n)(a)n! (x−a)n+f(N+1)(z)(N+1)!

What is the power series of Sinx?

The sine function has the power series expansion: sinx. = ∞∑n=0(−1)nx2n+1(2n+1)!


2 Answers

Would this article help you?

http://www.coranac.com/2009/07/sines/

It has a couple of algorithms for computing approximate sin(x) values, with both C and assembly versions. Granted, it's ARM assembly, but the gist of it should translate easily to x86 or similar.

like image 95
Amber Avatar answered Sep 24 '22 05:09

Amber


You don't state which CPU architecture so I'm assuming x86.

The simplist (and possibly most inefficient) way would be to write the formula in RPN, which can be mapped almost directly to FPU instructions.

Example,

algebraic formula : x - (x^3/3!) + (x^5/5!)

RPN : x x x * x * 3 2 * / - x x * x * x * x * 5 4 * 3 * 2 * / +

which becomes :

fld x
fld x
fld x
fmul
fld x
fmul
fild [const_3]
fild [const_2]
fmul
fdiv
fsub
fld x
fld x
fmul 
fld x
fmul
fld x
fmul
fld x
fmul
fild [const_5]
fild [const_4]
fmul
fild [const_3]
fmul
fild [const_2]
fmul
fdiv
fadd

There are some obvious optimisation strategies -

  • instead of calculating x, xxx, xxxxx etc for each term, store a 'running product' and just multiply by x*x each time
  • instead of calculating the factorial for each term, do the same 'running product'

Here's some commented code for x86 FPU, the comments after each FPU instruction show the stack state after that instruction has executed, with the stack top (st0) on the left, eg :

fldz ; 0
fld1 ; 1, 0

--snip--

bits 32

section .text

extern printf
extern atof
extern atoi
extern puts
global main

taylor_sin:
  push eax
  push ecx

  ; input :
  ;  st(0) = x, value to approximate sin(x) of
  ;  [esp+12] = number of taylor series terms

  ; variables we'll use :
  ; s = sum of all terms (final result)
  ; x = value we want to take the sin of
  ; fi = factorial index (1, 3, 5, 7, ...)
  ; fc = factorial current (1, 6, 120, 5040, ...)
  ; n = numerator of term (x, x^3, x^5, x^7, ...)

  ; setup state for each iteration (term)
  fldz ; s x
  fxch st1 ; x s
  fld1 ; fi x s
  fld1 ; fc fi x s
  fld st2 ; n fc fi x s

  ; first term
  fld st1 ; fc n fc fi x s
  fdivr st0,st1 ; r n fc fi x s
  faddp st5,st0 ; n fc fi x s

  ; loop through each term
  mov ecx,[esp+12] ; number of terms
  xor eax,eax ; zero add/sub counter

loop_term:
  ; calculate next odd factorial
  fld1 ; 1 n fc fi x s
  faddp st3 ; n fc fi x s
  fld st2 ; fi n fc fi x s
  fmulp st2,st0
  fld1 ; 1 n fc fi x s
  faddp st3 ; n fc fi x s
  fld st2 ; fi n fc fi x s
  fmulp st2,st0 ; n fc fi x s

  ; calculate next odd power of x
  fmul st0,st3 ; n*x fc fi x s
  fmul st0,st3 ; n*x*x fc fi x s

  ; divide power by factorial
  fld st1 ; fc n fc fi x s
  fdivr st0,st1 ; r n fc fi x s

  ; check if we need to add or subtract this term
  test eax,1
  jnz odd_term
  fsubp st5,st0 ; n fc fi x s
  jmp skip
odd_term:
  ; accumulate result
  faddp st5,st0 ; n fc fi x s
skip:
  inc eax ; increment add/sub counter
  loop loop_term

  ; unstack work variables
  fstp st0
  fstp st0
  fstp st0
  fstp st0

  ; result is in st(0)

  pop ecx
  pop eax

  ret

main:

  ; check if we have 2 command-line args
  mov eax, [esp+4]
  cmp eax, 3
  jnz error

  ; get arg 1 - value to calc sin of
  mov ebx, [esp+8]
  push dword [ebx+4]
  call atof
  add esp, 4

  ; get arg 2 - number of taylor series terms
  mov ebx, [esp+8]
  push dword [ebx+8]
  call atoi
  add esp, 4

  ; do the taylor series approximation
  push eax
  call taylor_sin
  add esp, 4

  ; output result
  sub esp, 8
  fstp qword [esp]
  push format
  call printf
  add esp,12

  ; return to libc
  xor eax,eax
  ret

error:
  push error_message
  call puts
  add esp,4
  mov eax,1
  ret

section .data

error_message: db "syntax: <x> <terms>",0
format: db "%0.10f",10,0

running the program :

$ ./taylor-sine 0.5 1
0.4791666667
$ ./taylor-sine 0.5 5
0.4794255386
$ echo "s(0.5)"|bc -l
.47942553860420300027
like image 35
matja Avatar answered Sep 22 '22 05:09

matja