For an example, for the array [1-23] there are 6 cases when Farey number of steps are lesser than Binary search; in Fibonacci search there are 4 cases when this search produce number of steps lesser than Binary search.
Here is a code that was used for Farey search vs. Binary search:
# include
# include
# include
# include
# include
# include
//# include
# define MAX 100000
long int a,a_aux,b_aux,b,mij,mij_v,v_N[3],v_D[3];
//[0] pt a, [1] pt mij, [2] pt b
long int a2,b2,mij2;
int opt;
long int r,scb,scbf;
unsigned long int c=0;
long int i,val;
long int huge v[MAX];
time_t t1,t2;
struct time t3,t4;
long int ncb,ncbf,o;
void main()
{
clrscr();
opt=0;
while(opt!=3)
{
clrscr();
cout<<"Please choose an option :\n";
cout<<"\t1. Binary search\n";
cout<<"\t2. Binary search using the FAREY addition\n";
cout<<"\t3. Enter the interval\n";
cout<<"\t4. END of the PROGRAM\n";
cin>>opt;
if(opt!=3) cout<<"\a";
}
while(opt<=3)
{
c=1;
if(opt==3)
{
cout<<"Enter a,b :\n";
cin>>a>>b;
a_aux=a;
b_aux=b;
for(i=a;i<=b+1;i++)
v[i-a]=i;
cout<<"The searched value will be each value of the interval... ";
//cin>>val;
getche();
}
if(opt<=2)
{
r=0;
scb=0;
scbf=0;
for(i=a_aux+1;i<=b_aux;i++)
{
ncb=1;
ncbf=1;
val=i;
//if(val==176) exit(1);
for(o=1;o<=2;o++)
{
opt=o;
a=a_aux;
b=b_aux;
mij2=(a+b)/2;
//initializari
if(opt==1) mij=(a+b)/2;
else if(opt==2)
{
v_N[0]=a;
v_D[0]=1;
v_N[2]=b;
v_D[2]=1;
v_N[1]=v_N[0]+v_N[2];
v_D[1]=v_D[0]+v_D[2];
mij=v_N[1]/v_D[1];
}
c=0;
a2=a;
b2=b;
mij2=(a2+b2)/2;
t1=time(NULL);
gettime(&t3);
while(
(val!=v[mij2])
&&(val!=v[mij])
&&(val!=v[a])
&&(val!=v[b])
)
{
if(opt==1)
{
if(val
mij2=(a+b)/2;
}
else if(opt==2)
{
if(val
if(val>v[mij])
{
a=mij;
b=mij2;
v_N[0]=v_N[1];
v_D[0]=v_D[1];
v_N[2]=(a+b);
v_D[2]=2;
}
else //val
if(mij
b=mij;
v_N[2]=v_N[1];
v_D[2]=v_D[1];
}
else
{
b=mij2;
v_N[2]=a2+b2;
v_D[2]=2;
}
}
b2=mij2;
}
else if(val>v[mij2])
{
if(val
a=mij2;
b=mij;
v_N[0]=a+b;
v_D[0]=2;
v_N[2]=v_N[1];
v_D[2]=v_D[1];
}
else//val>v[mij] and val>v[mij2], mij ? mij2
{
if(mij>mij2)
{
a=mij;
v_N[0]=v_N[1];
v_D[0]=v_D[1];
}
else
{
a=mij2;
v_N[0]=a2+b2;
v_D[0]=2;
}
}
a2=mij2;
}
v_N[1]=v_N[0]+v_N[2];
v_D[1]=v_D[0]+v_D[2];
mij=v_N[1]/v_D[1];
mij2=(a2+b2)/2;
}
c++;
}
if(o==1) {ncb=c;}
else {ncbf=c;}
t2=time(NULL);
gettime(&t4);
}
if(ncb
if(ncb>ncbf)
{
r++;
scb+=ncb;
scbf+=ncbf;
}
}
float pc=0.0,pro=0.0;
pro=((float)scb)/scbf;
pc=(r*100.0)/(b_aux-a_aux+1);
cout<<"\nCBF < CB for "<
getche();
}
clrscr();
cout<<"Please choose an option :\n";
cout<<"\t1. Binary search\n";
cout<<"\t2. Binary search using the FAREY addition\n";
cout<<"\t3. Enter the interval\n";
cout<<"\t4. END of the PROGRAM\n";
cin>>opt;
}
}
Fibonacci search program
///////////////////////////////////////////////////////////////////////////////////////
//////
////// Fibonaccian search in an ordered array
////// This program can be downloaded from http://www.ics.forth.gr/~lourakis/fibsrch/
////// Copyright (C) 2005 Manolis Lourakis (lourakis AT .DeleteThis.ics.forth.gr)
////// Institute of Computer Science, Foundation for Research & Technology - Hellas
////// Heraklion, Crete, Greece.
//////
////// This program is free software; you can redistribute it and/or modify
////// it under the terms of the GNU General Public License as published by
////// the Free Software Foundation; either version 2 of the License, or
////// (at your option) any later version.
//////
////// This program is distributed in the hope that it will be useful,
////// but WITHOUT ANY WARRANTY; without even the implied warranty of
////// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
////// GNU General Public License for more details.
//////
///////////////////////////////////////////////////////////////////////////////////////
#include
#include
#include
#include
//#include "fibsrch.h"
int s1 = 0;
int s2 = 0;
int data[]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23};
int i, x, n, val;
/*
* If val is found in arr, return the index of its location in arr.
* Otherwise, return the index of the smallest element greater than val
*/
static int binsrch_geq(const int *arr, int n, int val)
{
register int low, high, mid;
int geq;
low=0; high=n-1; geq=-1;
/* binary search for finding the element with value val */
while(low<=high){
s2++;
mid=(low+high)>>1; //(low+high)/2;
if(val
geq=mid;
}
else if(val>arr[mid])
low=mid+1;
else
return mid; /* found */
}
return geq; /* not found */
}
/*
Fibonaccian search for locating the index of "val" in an array "arr" of size "n"
that is sorted in ascending order. See http://doi.acm.org/10.1145/367487.367496
Algorithm description
-----------------------------------------------------------------------------
Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and
F0 = 0, F1 = 1. To test whether an item is in a list of n = Fm ordered numbers,
proceed as follows:
a) Set k = m.
b) If k = 0, finish - no match.
c) Test item against entry in position Fk-1.
d) If match, finish.
e) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n.
Set k = k - 1 and go to b).
f) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1.
Renumber remaining entries from 1 to Fk-2, set k = k - 2 and go to b)
If Fm>n then the original array is augmented with Fm-n numbers larger
than val and the above algorithm is applied.
*/
int fibsrch(const int *arr, int n, int val)
{
register int k, idx, offs;
static int prevn=-1, prevk=-1;
/* Precomputed Fibonacci numbers F0 up to F46. This implementation assumes that the size n
* of the input array fits in 4 bytes. Note that F46=1836311903 is the largest Fibonacci
* number that is less or equal to the 4-byte INT_MAX (=2147483647). The next Fibonacci
* number, i.e. F47, is 2971215073 and is larger than INT_MAX, implying that it does not
* fit in a 4 byte integer. Note also that the last array element is INT_MAX rather than
* F47. This ensures correct operation for n>F46.
*/
const static int Fib[47+1]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903, INT_MAX};
/* find the smallest fibonacci number that is greater or equal to n. Store this
* number to avoid recomputing it in the case of repetitive searches with identical n.
*/
if(n!=prevn){
#if 1
k=(n>1)? binsrch_geq(Fib, sizeof(Fib)/sizeof(int), n) : 1;
#else /* the above binary search call can be substituted by the following code fragment: */
{
register int f0, f1, t;
for(f0=0, f1=1, k=1; f1
}
#endif
prevk=k;
prevn=n;
}
else k=prevk;
/* If the sought value is larger than the largest Fibonacci number less than n,
* care must be taken top ensure that we do not attempt to read beyond the end
* of the array. If we do need to do this, we pretend that the array is padded
* with elements larger than the sought value.
*/
for(offs=0; k>0; ){
//s1++;
idx=offs+Fib[--k];
/* note that at this point k has already been decremented once */
if(idx>=n || val
else if (val>arr[idx]){ // val in 2nd part
s1++;
offs=idx;
--k;
}
else // val==arr[idx], found
return idx;
}
return -1; // not found
}
#if 1
/* Sample driver program for fibsrch() */
void main(void)
{
for(val=1;val<=n;val++)
{
x=val; n=sizeof(data)/sizeof(int);
i=fibsrch(data, n, x);
if(i>=0)
printf("%d found at index %d\n", x, i);
else
printf("%d was not found\n", x);
printf("\nFIB search steps = %d",s1);
/****************************************/
i=binsrch_geq(data, n, x);
if(i>=0)
printf("%d found at index %d\n", x, i);
else
printf("%d was not found\n", x);
printf("\nBIN search steps = %d",s2);
printf("\n--------------------------------\n");
s1 = 0;
s2 = 0;
}
getche();
}
#endif
References
http://en.wikipedia.org/wiki/Fibonacci_search_technique
http://www.ics.forth.gr/~lourakis/fibsrch/#Algo
FAREY Search vs Binary Search
Some values can be found faster usinf the Farey addition than using the classic algorithm.
# include
# include
# include
# include
# include
# include
# define MAX 10000
int a,a_aux,b_aux,b,mij,mij_v,v_N[3],v_D[3];
//[0] pt a, [1] pt mij, [2] pt b
int a2,b2,mij2;
int opt;
unsigned long int c=0;
int i,val,v[MAX];
struct time t3,t4;
void main()
{
clrscr();
opt=0;
while(opt!=3)
{
clrscr();
cout<<"Please choose an option :\n";
cout<<"\t1. Binary search\n";
cout<<"\t2. Binary search using the FAREY addition\n";
cout<<"\t3. Enter the interval\n";
cout<<"\t4. END THE PROGRAM\n";
cin>>opt;
if(opt!=3) cout<<"\a";
}
while(opt<=3)
{
c=1;
if(opt==3)
{
cout<<"Please enter a,b :\n";
cin>>a>>b;
a_aux=a;
b_aux=b;
for(i=a;i<=b+1;i++)
v[i-a]=i;
cout<<"Please enter the shearched value: ";
cin>>val;
}
if(opt<=2)
{
a=a_aux;
b=b_aux;
mij=(a+b)/2;
//initializari
if(opt==1) mij=(a+b)/2;
else if(opt==2)
{
v_N[0]=a;
v_D[0]=1;
v_N[2]=b;
v_D[2]=1;
v_N[1]=v_N[0]+v_N[2];
v_D[1]=v_D[0]+v_D[2];
mij=v_N[1]/v_D[1];
}
c=0;
mij_v=0;
a2=a;
b2=b;
mij2=(a2+b2)/2;
time_t t1,t2;
t1=time(NULL);
gettime(&t3);
int q,r;
while(
v[mij]!=val
)
{
r=0;
if(v[a]==val) mij=a;
else if(v[b]==val) mij=b;
else if(v[mij2]==val) mij=mij2;
else
{
q=0;
if(opt==2)
{
if((mij
a2=a=mij2;
v_N[0]=v_N[1];
v_D[0]=v_D[1];
b2=b=mij;
v_N[2]=mij;
v_D[2]=1;
q=1;
}
else
if((mij2
b2=b=mij2;
v_N[2]=v_N[1];
v_D[2]=v_D[1];
a2=a=mij;
v_N[0]=mij;
v_D[0]=1;
q=1;
}
}
if(q==0)
{
/*
if(opt==2)
{
a=a2;b=b2;
if(mij2
*/
if(v[(a2+b2)/2]==val)
{
mij=(a2+b2)/2;
v_N[0]=a2;
v_D[0]=1;
v_N[2]=b2;
v_D[2]=1;
v_N[1]=a2+b2;
v_D[1]=2;
}
else
{
if(opt==2)
if(v[mij]>val)
if(mij2
{
if(opt==1)
b=mij;
else
{
if(mij2
else
b=b2=mij2;
if(v[mij2]==val)
{
mij=mij2;
}
else
{
//Test if mij_FAREY < mij_Bisectie
if(v[mij]<=v[(a+b)/2])
{
//F(a) * F(mij) < 0
v_N[2]=v_N[1];
v_D[2]=v_D[1];
b=v_N[2]/v_D[2];
}
// mij_FAREY >= mij_Bisectie
else
{
if((v[mij]<=val)&&(val<=v[(a+b)/2]))
{
v_N[0]=a+b;
v_D[0]=2;
v_N[2]=v_N[1];
v_D[2]=v_D[1];
a2=a=v_N[0]/v_D[0];
b2=b=v_N[2]/v_D[2];
}
else if((v[a]<=val)&&(val<=v[(a+b)/2]))
{
v_N[2]=a+b;
v_D[2]=2;
b2=b=v_N[2]/v_D[2];
}
}
}
}
}
else if((v[mij]<=val)&&(val<=v[b]))
{
if(opt==1)
a=mij;
else
{
if(mij2
else
a=a2=mij;
if(v[mij2]==val)
mij=mij2;
else
{
//Testez daca mij_FAREY < mij_Bisectie
if(mij<=(a+b)/2)
{
if((v[mij]<=val)&&(val<=v[(a+b)/2]))
{
// F(mij) * F((a+b)/2) < 0
v_N[0]=v_N[1];
v_D[0]=v_D[1];
v_N[2]=a+b;
v_D[2]=2;
a2=a=v_N[0]/v_D[0];
b2=b=v_N[2]/v_D[2];
}
else // F(mij) * F(b) < 0
{
v_N[0]=a+b;
v_D[0]=2;
a2=a=v_N[0]/v_D[0];
}
}
// mij_FAREY >= mij_Bisectie
else
{
// F(mij) * F(b) < 0
v_N[0]=v_N[1];
v_D[0]=v_D[1];
a2=a=v_N[0]/v_D[0];
}
}
}
}
}
}
if(opt==1) {mij_v=mij; mij=(a+b)/2;}
else
{
mij2=(a2+b2)/2;
if(mij2
if(v[(a2+b2)/2]==val)
{
v_N[0]=a2;
v_D[0]=1;
v_N[2]=b2;
v_D[2]=1;
v_N[1]=a2+b2;
v_D[1]=2;
mij=(a2+b2)/2;
}
else
{
if(r==0)
{
mij_v=mij;
v_N[1]=v_N[0]+v_N[2];
v_D[1]=v_D[0]+v_D[2];
mij=(v_N[0]+v_N[2])/(v_D[0]+v_D[2]);
}
}
}
c++;
}
}
cout<<"\nNo. of iteration of the program: "<
t2=time(NULL);
gettime(&t4);
cout<<"\n\n";
printf("Time of execution in second : %f\n",difftime(t2,t1));
printf("System clock before execution is: %2d:%02d:%02d.%02d\n",
t3.ti_hour, t3.ti_min, t3.ti_sec, t3.ti_hund);
printf("System clock after execution is: %2d:%02d:%02d.%02d\n",
t4.ti_hour, t4.ti_min, t4.ti_sec, t4.ti_hund);
getche();
}
clrscr();
cout<<"Please choose an option :\n";
cout<<"\t1. Binary search\n";
cout<<"\t2. Binary search using the FAREY addition\n";
cout<<"\t3. Enter the interval\n";
cout<<"\t4. END THE PROGRAM\n";
cin>>opt;
}
}
No comments:
Post a Comment