Skip to content

Instantly share code, notes, and snippets.

@rygorous
Created May 20, 2017 11:22
Embed
What would you like to do?
Useless Chebyshev!
; (NASM syntax)
; Evaluate the n-th Chebyshev polynomial of the first kind at x, T_n(x)
; On entry:
; x87 stack = (x)
; ecx = n
; On exit:
; x87 stack = (T_n(x))
; ecx destroyed
cheb:
sub ecx, 1
je .done ; n=1 case is identity
jb .n0
; General case: bootstrap the recurrence
fld1 ; -- 1 x
fld st1 ; -- x 1 x
fadd st ; -- 2x 1 x
fxch st2 ; -- x 1 2x
.recur: ; -- T_{n-1}(x) T_{n-2}(x) 2x
fld st2 ; -- 2x T_{n-1} T_{n-2} 2x
fmul st1 ; -- 2x*T_{n-1} T_{n-1} T_{n-2} 2x
fxch st2 ; -- T_{n-2} T_{n-1} 2x*T_{n-1} 2x
fsubp st2, st ; -- T_{n-1} T_n 2x
fxch st1 ; -- T_n T_{n-1} 2x (back to loop invariant)
dec ecx
jnz .recur
; clean temps off stack
fstp st2 ; -- T_{n-1} T_n
fstp st ; -- T_n
jmp .done
.n0:
fstp st
fld1
.done:
ret
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment