(long) Re: need help.
- To: mathgroup at smc.vnet.net
- Subject: [mg19136] (long) Re: [mg19086] need help.
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 5 Aug 1999 23:58:40 -0400
- References: <199908050535.BAA03396@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Ayad Soufiane wrote:
>
> I wrote this program for Mathematica 3.0 the logic seems to be correct, the
> output is not,
> do you have any idea about what is the problem ?
> The same program was run under a Windows machine using the new symbole
> \[Sum]\ of Mathematica 3, the output was different, it was giving a correct
> result without any problem,
> the thing is I need powerful unix machine to run this program, and the
> windows machine that I have is not fit for the job.
>
> Regards,
> Ayad Soufiane
>
> ---------------
> Listing of the Program
> ---------------
>
> Print[StringForm[" App. Num. "]];
> Print[StringForm["========================================================"]];
> For[ Split1=3, Split1 <5, Split1++,
> g=2;
> Beta1=1;
> nmax=Split1*(g-1);
> lng[x_]=Log[x]/Log[g];
> Pr[i_]=lng[1+1/i];
> c[Split1_]=lng[Split1+1];
> Start[Split1_]=g^(c[Split1]);
> End1[Split1_]=g^(c[Split1]+1)-1;
> TableSize[Split1_]=End1[Split1]-Start[Split1]+1;
> LoadFactor[N1_,Split1_]=N1/TableSize[Split1];
> Ro[i_,N1_]=1/N1;
> P[N1_,i_,j_]=Binomial[N1,j]*Pr[i]^(j)*(1-Pr[i])^(N1-j);
> Alpha1[i_,j_,k_,N1_]=If[i-1>=j-1,If[N1-1>=k-1,If[N1-i>=k-j,Binomial[i-1,j-1]*Binomial[N1-i,k-j]/Binomial[N1-1,k-1],0],0],0];
> Gamma1[k_,j_,N1_]=If[k>=j,Sum[Alpha1[i,j,k,N1]*Ro[i,N1],{i,j,N1}],0];
> q[N1_,h_,Split1_]=Sum[Pr[Ba]*Gamma1[j,h,N1]*P[N1,Ba,j],{Ba,Start[Split1],End1[Split1]},{j,1,N1}];
> S[N1_,Split1_]=Sum[h*q[N1,h,Split1],{h,1,N1}]/Sum[Pr[i]*P[N1,i,j],{i,Start[Split1],End1[Split1]},{j,1,N1}];
> Print[StringForm[" "]];
> Print[StringForm[" "]];
> Print[StringForm[" "]];
> Print[StringForm["-----------------------------------------------"]];
> Print[StringForm["* *"]];
> Print[StringForm["* Num. App. *"]];
> Print[StringForm["* *"]];
> Print[StringForm["-----------------------------------------------"]];
> Print[StringForm[" "]];
> Print[StringForm[" "]];
> Print[StringForm["Growth Factor g : "],g];
> Print[StringForm["Beta : "],Beta1];
> Print[StringForm["Split Number : "],Split1];
> Print[StringForm["Start File : "],N[Start[Split1]]];
> Print[StringForm["End File : "],N[End1[Split1]]];
> Print[StringForm["Table Size : "],N[TableSize[Split1]]];
> Print[StringForm["Load Factor Alpha :
> "],N[LoadFactor[nmax,Split1]]];
> Print[StringForm["Average Search Cost S("],N[nmax],StringForm[") :
> "],N[S[nmax,Split1]]];
> ]
>
> ----------
> Out-Put
> ----------
>
> Mathematica 3.0 for HP-UX PA-RISC
> Copyright 1988-97 Wolfram Research, Inc.
> -- Motif graphics initialized --
>
> In[1]:= App. Num.
>
> In[2]:=
> In[2]:= ========================================================
>
> In[3]:=
> In[3]:=
> $MaxExtraPrecision::meprec:
> In increasing internal precision while attempting to evaluate
> 1 + Log[4]/Log[2]
> Floor[-4 + 2 ], the limit $MaxExtraPrecision = 50.
> was reached. Increasing the value of $MaxExtraPrecision may help
> resolve
> the uncertainty.
>
> $MaxExtraPrecision::meprec:
> In increasing internal precision while attempting to evaluate
> 1 + Log[4]/Log[2]
> Floor[-4 + 2 ], the limit $MaxExtraPrecision = 50.
> was reached. Increasing the value of $MaxExtraPrecision may help
> resolve
> the uncertainty.
>
> $MaxExtraPrecision::meprec:
> In increasing internal precision while attempting to evaluate
> 1 + Log[4]/Log[2]
> Floor[-4 + 2 ], the limit $MaxExtraPrecision = 50.
> was reached. Increasing the value of $MaxExtraPrecision may help
> resolve
> the uncertainty.
>
> General::stop: Further output of $MaxExtraPrecision::meprec
> will be suppressed during this calculation.
>
> -----------------------------------------------
> * *
> * Num. App. *
> * *
> -----------------------------------------------
>
> Growth Factor g : 2
> Beta : 1
> Split Number : 3
> Start File : 4.
> End File : 7.
> Table Size : 4.
> Load Factor Alpha : 0.75
>
> 1
> Power::infy: Infinite expression - encountered.
> 0
>
> Infinity::indet:
> Indeterminate expression
> 1
> Log[1 + -]
> i 3
> 0 ComplexInfinity (Log[2] + <<1>>) <<1>> (1 - ----------)
> Log[2]
> ---------------------------------------------------------- encountered.
> 1 2 1
> Pi Log[2] (Log[2] - Log[1 + -]) Log[1 + -]
> i i
> Average Search Cost S(3.) : Indeterminate
>
> -----------------------------------------------
> * *
> * Num. App. *
> * *
> -----------------------------------------------
>
> Growth Factor g : 2
> Beta : 1
> Split Number : 4
> Start File : 5.
> End File : 9.
> Table Size : 5.
> Load Factor Alpha : 0.8
>
> 1
> Power::infy: Infinite expression - encountered.
> 0
>
> Infinity::indet:
> Indeterminate expression
> 1
> Log[1 + -]
> i 4
> 0 ComplexInfinity (Log[2] + <<1>>) <<1>> (1 - ----------)
> Log[2]
> ---------------------------------------------------------- encountered.
> 1 2 1
> Pi Log[2] (Log[2] - Log[1 + -]) Log[1 + -]
> i i
> Average Search Cost S(4.) : Indeterminate
>
> In[4]:=
> In[4]:=
>
> ______________________________________________________
> Get Your Private, Free Email at http://www.hotmail.com
I doubt the logic is in any sense correct but it is very hard to say for
certain because you do not give any indication of what might be the
desired results. Nor do you say what you have done to debug or otherwise
pin down the problematic areas. Let me make a few suggestions. Okay,
alot of suggestions.
I Clarity and readability
(i) Use tabs and spaces in some appropriate fashion.
(ii) Avoid capitalizing your variables and procedures because the
built-in ones are capitalized.
(iii) Never use one-letter procedure or variable names except for
iterators.
(iv) Use InputForm when you post code to the news group or to colleagues
(you did this, I just wanted to emphasize the importance).
(v) MOST IMPORTANTLY: Include commentary to give some idea of what
exactly you think your function should do.
(vi) In addition to saying what you expect the code to do and what you
have done to debug it, you might consider a title for your request more
suggestive than the one you chose.
II General coding
(i) Do not mix pattern names with loop iterators e.g. the following is a
bad idea:
For [split1=1,...,
myfunction[split1_] = ...
(ii) Do not put function definitions inside a loop unless there is a
good reason to do so e.g. they need to be dynamically redefined. So far
as I can tell there is no such need in your case.
(iii) Do not use StringForm inside Print statements unless you really
need it (you do not).
(iv) Do not redefine variables inside a loop unless the values might
change. For example, the statement
g = 2;
should not be in the loop.
(v) Get rid of unused variables. For example
beta1 = 1;
appears but beta1 is not used in any meaningful way elsewhere in the
code you posted.
(vi) If a variable has a value that remains unchanged, (e.g. g is always
2 in your code) consider whether you really want it to be a variable.
Good reasons might be
(a) You want it to have a mnemonic name (but g hardly qualifies)
(b) You plan to extend the code in such a way that different values
might
be used.
(vii) You should consider putting the initialization of variables and
the main loop inside a module, localizing the variables and thus making
a general procedure of the raw code.
III Debugging
(i) Look at the warning/error messages. Try to figure out why they
appear, what they might be telling you. If need be, insert Print
statements to isolate where they occur and figure out what is the cause.
(ii) More generally, use Print statements to insure that various
intermediate values are what you expect them to be.
(iii) When one procedure calls others, it is frequently a good idea to
first check them with reasonable inputs (this in effect modularizes the
problem-isolation step).
(iv) In this instance a small amount of debugging would have shown you
that the Floor computation causaes trouble. Why? Because it can fail to
evaluate to a number when faced with a symbolic expression that happens
to be an exact integer. This is not exactly a surprise since Floor is
discontinuous at the integers. There is an easy fix for this sort of
situation: add a bit of positive fuzz sufficiently small that it will
not bump any non-integers you plan to use above the next higher integer.
IV Other issues with this particular code
(i) I noticed the procedure
Ro[i_,N1_]=1/N1;
which means it is independent of i. I am assuming you meant i/N1 rather
than 1/N1 and changed it accordingly. Either way you should just use
division and not make a separate procedure, as this adds unnecessary
complexity to the code.
(ii) Your alpha procedure is a bit more intricate than is necessary. You
can simplify conditions such as i-1>=-j-1 in a fairly obvious way. Also
by reversing the inequalities you can have the zero values placed more
conveniently, which aids readability.
V Efficiency
(i) To make it simpler you should judiciously use numeric approximations
in the intermediate steps rather than only at the bitter end. This makes
little difference in your program for the experiments I tried but
avoiding costly and ultimately useless symbolic algorithms might be to
your advantage on larger examples.
(ii) You do not need a powerful Unix workstation to run this, any PC
that can run Mathematica will suffice. As demonstrated below. Do not
assume you need more computational resources unless you have an
excellent reason to believe your code is (to within some reasonable
factor) as efficient as possible (perhaps short of recoding it using
algorithms that may be much harder to implement). Sys-admins get real
suspicious of folks who bring machines to their silicon knees running
needlessly convoluted code.
All that said, below is my rewrite of your code. I did not put it into a
Module primarily because there was insufficient comments for me to
decide what exactly the appropriate inputs might be. Appears to be
measuring average-case efficiency of some flavor of hash table? Hard to
say. I took the liberty of letting split1 vary from 3 to 11 as 3 to 4
did not seem like much of a test. Also I timed each iteration through
the loop and returned the timings in a table.
g = 2;
lng[x_] = Log[g,x];
pr[i_] = lng[1+1/i];
pp[n1_,i_,j_] = Binomial[n1,j]*pr[i]^j*(1-pr[i])^(n1-j);
ro[i_,n1_] = i/n1; (* ??? *)
alpha1[i_,j_,k_,n1_] =
If [i<j, 0,
If [n1<k, 0,
If [n1-i<k-j, 0,
Binomial[i-1,j-1]*Binomial[n1-i,k-j]/Binomial[n1-1,k-1]]]];
gamma1[k_,j_,n1_] = If [k>=j, Sum[N[alpha1[i,j,k,n1]]*ro[i,n1],
{i,j,n1}], 0];
loadFactor[n1_, siz_] = n1/siz;
qq[n1_,h_,st_,en_] := Sum[pr[ba]*gamma1[j,h,n1*pp[n1,ba,j]],
{ba,st,en}, {j,1,n1}];
ss[n1_,st_,en_] := Sum[h*qq[n1,h,st,en], {h,1,n1}] /
Sum[pr[i]*pp[n1,i,j], {i,st,en}, {j,1,n1}];
Print["========================================================"];
epsilon = .0001;
Table[Timing[
nmax = split1*(g-1);
cc = Floor[lng[split1+1]+epsilon];
start = g^cc;
end1 = g^(cc+1)-1;
tableSize = end1-start+1;
loadf = loadFactor[nmax, tableSize];
Print[" "];
Print[" "];
Print[" "];
Print["-----------------------------------------------"];
Print["* *"];
Print["* Numeric values *"];
Print["* *"];
Print["-----------------------------------------------"];
Print[" "];
Print[" "];
Print["Growth Factor g : ", g];
Print["Split Number : ", split1];
Print["Start File : ", start];
Print["End File : ", end1];
Print["Table Size : ", tableSize];
Print["Load Factor Alpha : ", loadf];
Print["Average Search Cost S(", nmax, ") : ", ss[nmax,start,end1]]],
{split1, 3, 11}]
Just to show it appears to give reasonable results in reasonable time,
here is the output.
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 3
Start File : 4
End File : 7
Table Size : 4
3
Load Factor Alpha : -
4
Average Search Cost S(3) : 1.36039
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 4
Start File : 4
End File : 7
Table Size : 4
Load Factor Alpha : 1
Average Search Cost S(4) : 0.880084
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 5
Start File : 4
End File : 7
Table Size : 4
5
Load Factor Alpha : -
4
Average Search Cost S(5) : 1.21906
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 6
Start File : 4
End File : 7
Table Size : 4
3
Load Factor Alpha : -
2
Average Search Cost S(6) : 1.35084
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 7
Start File : 8
End File : 15
Table Size : 8
7
Load Factor Alpha : -
8
Average Search Cost S(7) : 1.80364
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 8
Start File : 8
End File : 15
Table Size : 8
Load Factor Alpha : 1
Average Search Cost S(8) : 3.24058
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 9
Start File : 8
End File : 15
Table Size : 8
9
Load Factor Alpha : -
8
Average Search Cost S(9) : 3.61525
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 10
Start File : 8
End File : 15
Table Size : 8
5
Load Factor Alpha : -
4
Average Search Cost S(10) : 3.84575
-----------------------------------------------
* *
* Numeric values *
* *
-----------------------------------------------
Growth Factor g : 2
Split Number : 11
Start File : 8
End File : 15
Table Size : 8
11
Load Factor Alpha : --
8
Average Search Cost S(11) : 5.37875
Out[145]= {{0.07 Second, Null}, {0.12 Second, Null}, {0.16 Second,
Null},
> {0.23 Second, Null}, {0.61 Second, Null}, {0.79 Second, Null},
> {0.98 Second, Null}, {1.21 Second, Null}, {1.53 Second, Null}}
- References:
- need help.
- From: "Ayad Soufiane" <ayad_s@hotmail.com>
- need help.