%%%off % Copyright: This file is part of the MMIX Supplement package (c) Martin Ruckert 2014 % File: 6.2.1/fsearch2.mms % Author: M. Ruckert % Title: Program F, Fibonaccian search % simple Fibonacci search PREFIX :fsearch: key IS \$0 Parameter. k IS \$1 i IS \$2 p IS \$3 q IS \$4 ki IS \$5 t IS \$6 %%%on F4A ADD i,i,q C_2-S-A & \ut F4. Increase \$i\$.\\ \$i\is i+q\$.\lineref|6.2.1fsearch2.astart| SUB p,p,q C_2-S-A & \$p\is p-q\$. SUB q,q,p C_2-S-A & \$q\is q-p\$. %%% :Search LDO ki,key,i C &\ut F2. Compare.\\ CMP t,k,ki C & PBN t,F3A C\bg{C_2} & To F3 if \$K< K_i\$. BZ t,Success C_2\bg{S} & Exit if \$K= K_i\$. %%% CMP t,p,8 C_2-S & PBNZ t,F4A C_2-S\bg{A} & To F4 if \$p\ne 1\$. POP 0,0 & Exit if not in table. %%% F3A SUB i,i,q C_1 & \ut F3. Decrease \$i\$.\\ \$i\is i-q\$. SUB p,p,q C_1 & \$p\is p-q\$. PBP q,F2B C_1\bg{1-S-A} & Swap registers if \$q>0\$. \lineref|6.2.1fsearch2.aend| POP 0,0 & Exit if not in table. %%% F4B ADD i,i,p & \lineref|6.2.1fsearch2.bstart|(Lines |6.2.1fsearch2.bstart|--|6.2.1fsearch2.bend| are SUB q,q,p &\hfill parallel to |6.2.1fsearch2.astart|--|6.2.1fsearch2.aend|.) SUB p,p,q %%% F2B LDO ki,key,i CMP t,k,ki PBN t,F3B BZ t,Success %%% CMP t,q,8 PBNZ t,F4B POP 0,0 %%% F3B SUB i,i,p SUB q,q,p PBP p,:Search \lineref|6.2.1fsearch2.bend| %%% POP 0,0 Success ADDU \$0,key,i S & Return \.LOC(\$K_i\$).. POP 1,0 &\slug %%%off PREFIX :