Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #29208 > unrolled thread

Improve speed calculations?

Started byjonas.thornvall@gmail.com
First post2016-01-10 05:33 -0800
Last post2016-01-11 06:48 -0800
Articles 10 — 3 participants

Back to article view | Back to comp.lang.javascript

Contents

  Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-10 05:33 -0800
    Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 03:19 -0800
      Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 04:41 -0800
      Re: Improve speed calculations? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-11 13:28 +0000
        Re: Improve speed calculations? Silvio <silvio@internet.com> - 2016-01-11 15:41 +0100
          Re: Improve speed calculations? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-11 15:44 +0000
            Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 07:53 -0800
            Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 07:56 -0800
            Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 08:28 -0800
        Re: Improve speed calculations? jonas.thornvall@gmail.com - 2016-01-11 06:48 -0800

#29208 — Improve speed calculations?

Fromjonas.thornvall@gmail.com
Date2016-01-10 05:33 -0800
SubjectImprove speed calculations?
Message-ID<86bb6f49-d74d-426d-bc2a-5b4cd7199bf4@googlegroups.com>
<script language="Javascript">

/*ADD TWO VARIABLES USING CHOSEN BASE*/
function naiveAdd(base, arrOne, addTwo)
{
   addOne=arrOne.slice();
   //addTwo=arrTwo.slice(); 
   abigArr = addOne.length;
   asmallArr = addTwo.length;
   addResult = [];
   remainder = 0;
   for (i = 0; i < asmallArr; i ++ )
   {
      
      addOne[i] = addOne[i] + addTwo[i] + remainder;
      if (addOne[i] >= base)
      {  
         
         addOne[i] = addOne[i] - base;
         remainder = 1;
      
      }
      else
      {
         remainder = 0;
      }
   }
   // If strings of equal length but there is a remainder;
   while (remainder == 1 && addOne[i]==(base-1))
   {
      addOne[i] = 0;
      i++;
   }
   if (remainder == 1) {if (isNaN(addOne[i])) addOne[i] = 0; addOne[i] = addOne[i]+1;}
   return addOne;
}

/* COMPARE SIZE OF TWO ARRAYS, IF A < B RETURN TRUE, IF B >= A RETURN FALSE */
function lessThan(A, B)
{
   var AA = A.length;
   var BB = B.length;
   if(AA > BB) return false;
   if(AA < BB) return true;
   // AA = BB, compare indexes from biggest to smallest.
   for(i = AA - 1; i >= 0; i -- )
   {
      if(A[i] < B[i]) return true;
      if(A[i] > B[i]) return false;
   }
   return false;
}

/* ORDER THE ARRAYS SO THE BIGGER IS PASSED AS FIRST ARGUMENT*/
function orderArrayAdd(Abase, A, B)
{
   return lessThan(A, B) ? counterArr = naiveAdd(Abase, B, A) : counterArr = naiveAdd(Abase, A, B);
}

/* GET VALUES FROM INPUT*/
function fetchValues(){
base=document.eval.FBASE.value;
myeval = document.eval.expression.value;
lucasStart = document.eval.start.value;
lStart=parseInt(lucasStart)
lucasScope = document.eval.scope.value;
lScope=parseInt(lucasScope)
}

/* PARSE VALUES FROM INPUT */
function parseToInt(){
if (result = myeval.indexOf("+") != - 1)
   {
      opArr = myeval.split("+");
      operation = "+";
   }
   arrOne = opArr[0].split("").map(Number).reverse();
   arrTwo = opArr[1].split("").map(Number).reverse();
}


function main(){
document.eval.result.value="";
document.eval.timing.value="";

base=2;
evalStr="";
var out=[];counter=1;
fetchValues();
parseToInt();
flip=0;
/* TIMER START */
var start = new Date().getTime();
lEnd=lStart+lScope;

while(counter<=lEnd){
out=orderArrayAdd(base,arrOne,arrTwo);
arrOne=arrTwo.slice();
arrTwo=out.slice();
if (counter>=lStart && counter<lEnd) {fib=out.slice();evalStr+=counter+"th "+fib.reverse().join('')+"\n";}
counter++;
}
/* TIMER END */
var end = new Date().getTime();
var time = end - start;
document.eval.result.value+=evalStr;
document.eval.timing.value+=time;
} </script>

<html><body onLoad="main()";>
<H1>FIBONACCI AND OTHER SERIES</H1>
<form name="eval" onsubmit="main(); return false;">
<input type="submit" value="Generate"><input type="text" name="timing"  value="" size="4"> ms BASE<input type="text" name="FBASE"  value="2" size="2"><br>
Start print x'th number in Serie<input type="text" name="start" value="1" size="9"> How many follwing in Serie -><input type="text" name="scope" value="777" size="9"><br>
Generate Serie expansons using startvalues<input type="text" name="expression" value="1+1" size="10"><br>
Result <textarea name="result" cols="100" rows="30"></textarea><br>


</form>
</body></html>

[toc] | [next] | [standalone]

#29225

Fromjonas.thornvall@gmail.com
Date2016-01-11 03:19 -0800
Message-ID<69c96cdd-1020-470c-b0b2-66e2898468bb@googlegroups.com>
In reply to#29208
Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> <script language="Javascript">
> 
> /*ADD TWO VARIABLES USING CHOSEN BASE*/
> function naiveAdd(base, arrOne, addTwo)
> {
>    addOne=arrOne.slice();
>    //addTwo=arrTwo.slice(); 
>    abigArr = addOne.length;
>    asmallArr = addTwo.length;
>    addResult = [];
>    remainder = 0;
>    for (i = 0; i < asmallArr; i ++ )
>    {
>       
>       addOne[i] = addOne[i] + addTwo[i] + remainder;
>       if (addOne[i] >= base)
>       {  
>          
>          addOne[i] = addOne[i] - base;
>          remainder = 1;
>       
>       }
>       else
>       {
>          remainder = 0;
>       }
>    }
>    // If strings of equal length but there is a remainder;
>    while (remainder == 1 && addOne[i]==(base-1))
>    {
>       addOne[i] = 0;
>       i++;
>    }
>    if (remainder == 1) {if (isNaN(addOne[i])) addOne[i] = 0; addOne[i] = addOne[i]+1;}
>    return addOne;
> }
> 
> /* COMPARE SIZE OF TWO ARRAYS, IF A < B RETURN TRUE, IF B >= A RETURN FALSE */
> function lessThan(A, B)
> {
>    var AA = A.length;
>    var BB = B.length;
>    if(AA > BB) return false;
>    if(AA < BB) return true;
>    // AA = BB, compare indexes from biggest to smallest.
>    for(i = AA - 1; i >= 0; i -- )
>    {
>       if(A[i] < B[i]) return true;
>       if(A[i] > B[i]) return false;
>    }
>    return false;
> }
> 
> /* ORDER THE ARRAYS SO THE BIGGER IS PASSED AS FIRST ARGUMENT*/
> function orderArrayAdd(Abase, A, B)
> {
>    return lessThan(A, B) ? counterArr = naiveAdd(Abase, B, A) : counterArr = naiveAdd(Abase, A, B);
> }
> 
> /* GET VALUES FROM INPUT*/
> function fetchValues(){
> base=document.eval.FBASE.value;
> myeval = document.eval.expression.value;
> lucasStart = document.eval.start.value;
> lStart=parseInt(lucasStart)
> lucasScope = document.eval.scope.value;
> lScope=parseInt(lucasScope)
> }
> 
> /* PARSE VALUES FROM INPUT */
> function parseToInt(){
> if (result = myeval.indexOf("+") != - 1)
>    {
>       opArr = myeval.split("+");
>       operation = "+";
>    }
>    arrOne = opArr[0].split("").map(Number).reverse();
>    arrTwo = opArr[1].split("").map(Number).reverse();
> }
> 
> 
> function main(){
> document.eval.result.value="";
> document.eval.timing.value="";
> 
> base=2;
> evalStr="";
> var out=[];counter=1;
> fetchValues();
> parseToInt();
> flip=0;
> /* TIMER START */
> var start = new Date().getTime();
> lEnd=lStart+lScope;
> 
> while(counter<=lEnd){
> out=orderArrayAdd(base,arrOne,arrTwo);
> arrOne=arrTwo.slice();
> arrTwo=out.slice();
> if (counter>=lStart && counter<lEnd) {fib=out.slice();evalStr+=counter+"th "+fib.reverse().join('')+"\n";}
> counter++;
> }
> /* TIMER END */
> var end = new Date().getTime();
> var time = end - start;
> document.eval.result.value+=evalStr;
> document.eval.timing.value+=time;
> } </script>
> 
> <html><body onLoad="main()";>
> <H1>FIBONACCI AND OTHER SERIES</H1>
> <form name="eval" onsubmit="main(); return false;">
> <input type="submit" value="Generate"><input type="text" name="timing"  value="" size="4"> ms BASE<input type="text" name="FBASE"  value="2" size="2"><br>
> Start print x'th number in Serie<input type="text" name="start" value="1" size="9"> How many follwing in Serie -><input type="text" name="scope" value="777" size="9"><br>
> Generate Serie expansons using startvalues<input type="text" name="expression" value="1+1" size="10"><br>
> Result <textarea name="result" cols="100" rows="30"></textarea><br>
> 
> 
> </form>
> </body></html>

http://jt.node365.se/BAUTABASE.html

Using the biggest base possible adding "4503599627370495" encoding fibonacci in javascript without overflow.

Also fixed ambiguity reading out the numbers in bases over ten by using separator for digitplaces. The add can not cause overflow but to get rid of base overflow would require some real deep thinking.

The 100000th Fibonacci took 34 seconds i do not think i can get it much faster in javascript if your a wizard please prove me wrong.

http://jt.node365.se/BAUTABASE.html

[toc] | [prev] | [next] | [standalone]

#29226

Fromjonas.thornvall@gmail.com
Date2016-01-11 04:41 -0800
Message-ID<52374f60-802d-42ff-b891-b922a682dd76@googlegroups.com>
In reply to#29225
Den måndag 11 januari 2016 kl. 12:19:12 UTC+1 skrev jonas.t...@gmail.com:
> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> > <script language="Javascript">
> > 
> > /*ADD TWO VARIABLES USING CHOSEN BASE*/
> > function naiveAdd(base, arrOne, addTwo)
> > {
> >    addOne=arrOne.slice();
> >    //addTwo=arrTwo.slice(); 
> >    abigArr = addOne.length;
> >    asmallArr = addTwo.length;
> >    addResult = [];
> >    remainder = 0;
> >    for (i = 0; i < asmallArr; i ++ )
> >    {
> >       
> >       addOne[i] = addOne[i] + addTwo[i] + remainder;
> >       if (addOne[i] >= base)
> >       {  
> >          
> >          addOne[i] = addOne[i] - base;
> >          remainder = 1;
> >       
> >       }
> >       else
> >       {
> >          remainder = 0;
> >       }
> >    }
> >    // If strings of equal length but there is a remainder;
> >    while (remainder == 1 && addOne[i]==(base-1))
> >    {
> >       addOne[i] = 0;
> >       i++;
> >    }
> >    if (remainder == 1) {if (isNaN(addOne[i])) addOne[i] = 0; addOne[i] = addOne[i]+1;}
> >    return addOne;
> > }
> > 
> > /* COMPARE SIZE OF TWO ARRAYS, IF A < B RETURN TRUE, IF B >= A RETURN FALSE */
> > function lessThan(A, B)
> > {
> >    var AA = A.length;
> >    var BB = B.length;
> >    if(AA > BB) return false;
> >    if(AA < BB) return true;
> >    // AA = BB, compare indexes from biggest to smallest.
> >    for(i = AA - 1; i >= 0; i -- )
> >    {
> >       if(A[i] < B[i]) return true;
> >       if(A[i] > B[i]) return false;
> >    }
> >    return false;
> > }
> > 
> > /* ORDER THE ARRAYS SO THE BIGGER IS PASSED AS FIRST ARGUMENT*/
> > function orderArrayAdd(Abase, A, B)
> > {
> >    return lessThan(A, B) ? counterArr = naiveAdd(Abase, B, A) : counterArr = naiveAdd(Abase, A, B);
> > }
> > 
> > /* GET VALUES FROM INPUT*/
> > function fetchValues(){
> > base=document.eval.FBASE.value;
> > myeval = document.eval.expression.value;
> > lucasStart = document.eval.start.value;
> > lStart=parseInt(lucasStart)
> > lucasScope = document.eval.scope.value;
> > lScope=parseInt(lucasScope)
> > }
> > 
> > /* PARSE VALUES FROM INPUT */
> > function parseToInt(){
> > if (result = myeval.indexOf("+") != - 1)
> >    {
> >       opArr = myeval.split("+");
> >       operation = "+";
> >    }
> >    arrOne = opArr[0].split("").map(Number).reverse();
> >    arrTwo = opArr[1].split("").map(Number).reverse();
> > }
> > 
> > 
> > function main(){
> > document.eval.result.value="";
> > document.eval.timing.value="";
> > 
> > base=2;
> > evalStr="";
> > var out=[];counter=1;
> > fetchValues();
> > parseToInt();
> > flip=0;
> > /* TIMER START */
> > var start = new Date().getTime();
> > lEnd=lStart+lScope;
> > 
> > while(counter<=lEnd){
> > out=orderArrayAdd(base,arrOne,arrTwo);
> > arrOne=arrTwo.slice();
> > arrTwo=out.slice();
> > if (counter>=lStart && counter<lEnd) {fib=out.slice();evalStr+=counter+"th "+fib.reverse().join('')+"\n";}
> > counter++;
> > }
> > /* TIMER END */
> > var end = new Date().getTime();
> > var time = end - start;
> > document.eval.result.value+=evalStr;
> > document.eval.timing.value+=time;
> > } </script>
> > 
> > <html><body onLoad="main()";>
> > <H1>FIBONACCI AND OTHER SERIES</H1>
> > <form name="eval" onsubmit="main(); return false;">
> > <input type="submit" value="Generate"><input type="text" name="timing"  value="" size="4"> ms BASE<input type="text" name="FBASE"  value="2" size="2"><br>
> > Start print x'th number in Serie<input type="text" name="start" value="1" size="9"> How many follwing in Serie -><input type="text" name="scope" value="777" size="9"><br>
> > Generate Serie expansons using startvalues<input type="text" name="expression" value="1+1" size="10"><br>
> > Result <textarea name="result" cols="100" rows="30"></textarea><br>
> > 
> > 
> > </form>
> > </body></html>
> 
> http://jt.node365.se/BAUTABASE.html
> 
> Using the biggest base possible adding "4503599627370495" encoding fibonacci in javascript without overflow.
> 
> Also fixed ambiguity reading out the numbers in bases over ten by using separator for digitplaces. The add can not cause overflow but to get rid of base overflow would require some real deep thinking.
> 
> The 100000th Fibonacci took 34 seconds i do not think i can get it much faster in javascript if your a wizard please prove me wrong.
> 
> http://jt.node365.se/BAUTABASE.html

Oh it seem a bug slipped in.  Just 5 seconds for the 100000th fibonacci and 40 seconds for the 1 million th. But it seem it is bigger than windows clipboard handle.

http://jt.node365.se/fibonacci.html

[toc] | [prev] | [next] | [standalone]

#29227

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2016-01-11 13:28 +0000
Message-ID<87si24w8id.fsf@bsb.me.uk>
In reply to#29225
jonas.thornvall@gmail.com writes:

> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
>> <script language="Javascript">
<snip code>
> http://jt.node365.se/BAUTABASE.html
>
> Using the biggest base possible adding "4503599627370495" encoding
> fibonacci in javascript without overflow.
>
> Also fixed ambiguity reading out the numbers in bases over ten by
> using separator for digitplaces. The add can not cause overflow but to
> get rid of base overflow would require some real deep thinking.
>
> The 100000th Fibonacci took 34 seconds i do not think i can get it
> much faster in javascript if your a wizard please prove me wrong.

I have not tried your code, but I've just written a quick bignum add
function and I can get fib(100000) in about 3.5 seconds.  If I have time
to unravel yours, I'll do a comparative test.  Note that a language with
a good bignum type (Haskell, for example) will do it in less than 100th
of a second.

Note that your 'challenge' makes it easy to optimise the code.  For
example, using a power of 10 as the base makes the conversion for
printing very simple.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29228

FromSilvio <silvio@internet.com>
Date2016-01-11 15:41 +0100
Message-ID<5693bf11$0$23861$e4fe514c@news.xs4all.nl>
In reply to#29227
On 01/11/2016 02:28 PM, Ben Bacarisse wrote:
> jonas.thornvall@gmail.com writes:
>
>> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
>>> <script language="Javascript">
> <snip code>
>> http://jt.node365.se/BAUTABASE.html
>>
>> Using the biggest base possible adding "4503599627370495" encoding
>> fibonacci in javascript without overflow.
>>
>> Also fixed ambiguity reading out the numbers in bases over ten by
>> using separator for digitplaces. The add can not cause overflow but to
>> get rid of base overflow would require some real deep thinking.
>>
>> The 100000th Fibonacci took 34 seconds i do not think i can get it
>> much faster in javascript if your a wizard please prove me wrong.
>
> I have not tried your code, but I've just written a quick bignum add
> function and I can get fib(100000) in about 3.5 seconds.  If I have time
> to unravel yours, I'll do a comparative test.  Note that a language with
> a good bignum type (Haskell, for example) will do it in less than 100th
> of a second.
>
> Note that your 'challenge' makes it easy to optimise the code.  For
> example, using a power of 10 as the base makes the conversion for
> printing very simple.
>

That is well neigh impossible if you used a 10-based decimal since Jonas 
uses a huge base and is convinced that using a larger base will make 
computations much faster. Your result would invalidate that claim...

[toc] | [prev] | [next] | [standalone]

#29230

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2016-01-11 15:44 +0000
Message-ID<87fuy4w27e.fsf@bsb.me.uk>
In reply to#29228
Silvio <silvio@internet.com> writes:

> On 01/11/2016 02:28 PM, Ben Bacarisse wrote:
>> jonas.thornvall@gmail.com writes:
>>
>>> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
>>>> <script language="Javascript">
>> <snip code>
>>> http://jt.node365.se/BAUTABASE.html
>>>
>>> Using the biggest base possible adding "4503599627370495" encoding
>>> fibonacci in javascript without overflow.
>>>
>>> Also fixed ambiguity reading out the numbers in bases over ten by
>>> using separator for digitplaces. The add can not cause overflow but to
>>> get rid of base overflow would require some real deep thinking.
>>>
>>> The 100000th Fibonacci took 34 seconds i do not think i can get it
>>> much faster in javascript if your a wizard please prove me wrong.
>>
>> I have not tried your code, but I've just written a quick bignum add
>> function and I can get fib(100000) in about 3.5 seconds.  If I have time
>> to unravel yours, I'll do a comparative test.  Note that a language with
>> a good bignum type (Haskell, for example) will do it in less than 100th
>> of a second.
>>
>> Note that your 'challenge' makes it easy to optimise the code.  For
>> example, using a power of 10 as the base makes the conversion for
>> printing very simple.
>>
>
> That is well neigh impossible if you used a 10-based decimal since
> Jonas uses a huge base and is convinced that using a larger base will
> make computations much faster. Your result would invalidate that
> claim...

Using base 10 is quite slow (my code needs 23s for fib(100000) using
base 10), but I use a higher power of 10 as the base for speed whilst
keeping printing simple.  With higher powers, you do get faster results
(up to a limit, of course!).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29231

Fromjonas.thornvall@gmail.com
Date2016-01-11 07:53 -0800
Message-ID<56facf9e-f3c2-4286-9e67-23e3c45e8e9d@googlegroups.com>
In reply to#29230
Den måndag 11 januari 2016 kl. 16:44:32 UTC+1 skrev Ben Bacarisse:
> Silvio <silvio@internet.com> writes:
> 
> > On 01/11/2016 02:28 PM, Ben Bacarisse wrote:
> >> jonas.thornvall@gmail.com writes:
> >>
> >>> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> >>>> <script language="Javascript">
> >> <snip code>
> >>> http://jt.node365.se/BAUTABASE.html
> >>>
> >>> Using the biggest base possible adding "4503599627370495" encoding
> >>> fibonacci in javascript without overflow.
> >>>
> >>> Also fixed ambiguity reading out the numbers in bases over ten by
> >>> using separator for digitplaces. The add can not cause overflow but to
> >>> get rid of base overflow would require some real deep thinking.
> >>>
> >>> The 100000th Fibonacci took 34 seconds i do not think i can get it
> >>> much faster in javascript if your a wizard please prove me wrong.
> >>
> >> I have not tried your code, but I've just written a quick bignum add
> >> function and I can get fib(100000) in about 3.5 seconds.  If I have time
> >> to unravel yours, I'll do a comparative test.  Note that a language with
> >> a good bignum type (Haskell, for example) will do it in less than 100th
> >> of a second.
> >>
> >> Note that your 'challenge' makes it easy to optimise the code.  For
> >> example, using a power of 10 as the base makes the conversion for
> >> printing very simple.
> >>
> >
> > That is well neigh impossible if you used a 10-based decimal since
> > Jonas uses a huge base and is convinced that using a larger base will
> > make computations much faster. Your result would invalidate that
> > claim...
> 
> Using base 10 is quite slow (my code needs 23s for fib(100000) using
> base 10), but I use a higher power of 10 as the base for speed whilst
> keeping printing simple.  With higher powers, you do get faster results
> (up to a limit, of course!).
> 
> -- 
> Ben.

Is the limit of base for search x'th fiboniacci x/2 or square root x? I was thinking x/2 as the ideal base?

[toc] | [prev] | [next] | [standalone]

#29232

Fromjonas.thornvall@gmail.com
Date2016-01-11 07:56 -0800
Message-ID<58985c2c-1555-448d-9180-e513da33a0fc@googlegroups.com>
In reply to#29230
Den måndag 11 januari 2016 kl. 16:44:32 UTC+1 skrev Ben Bacarisse:
> Silvio <silvio@internet.com> writes:
> 
> > On 01/11/2016 02:28 PM, Ben Bacarisse wrote:
> >> jonas.thornvall@gmail.com writes:
> >>
> >>> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> >>>> <script language="Javascript">
> >> <snip code>
> >>> http://jt.node365.se/BAUTABASE.html
> >>>
> >>> Using the biggest base possible adding "4503599627370495" encoding
> >>> fibonacci in javascript without overflow.
> >>>
> >>> Also fixed ambiguity reading out the numbers in bases over ten by
> >>> using separator for digitplaces. The add can not cause overflow but to
> >>> get rid of base overflow would require some real deep thinking.
> >>>
> >>> The 100000th Fibonacci took 34 seconds i do not think i can get it
> >>> much faster in javascript if your a wizard please prove me wrong.
> >>
> >> I have not tried your code, but I've just written a quick bignum add
> >> function and I can get fib(100000) in about 3.5 seconds.  If I have time
> >> to unravel yours, I'll do a comparative test.  Note that a language with
> >> a good bignum type (Haskell, for example) will do it in less than 100th
> >> of a second.
> >>
> >> Note that your 'challenge' makes it easy to optimise the code.  For
> >> example, using a power of 10 as the base makes the conversion for
> >> printing very simple.
> >>
> >
> > That is well neigh impossible if you used a 10-based decimal since
> > Jonas uses a huge base and is convinced that using a larger base will
> > make computations much faster. Your result would invalidate that
> > claim...
> 
> Using base 10 is quite slow (my code needs 23s for fib(100000) using
> base 10), but I use a higher power of 10 as the base for speed whilst
> keeping printing simple.  With higher powers, you do get faster results
> (up to a limit, of course!).
> 
> -- 
> Ben.

What timing for the 1 million th Ben?

[toc] | [prev] | [next] | [standalone]

#29233

Fromjonas.thornvall@gmail.com
Date2016-01-11 08:28 -0800
Message-ID<ea93fc95-7ec2-4827-9f23-9beda487a7bb@googlegroups.com>
In reply to#29230
Den måndag 11 januari 2016 kl. 16:44:32 UTC+1 skrev Ben Bacarisse:
> Silvio <silvio@internet.com> writes:
> 
> > On 01/11/2016 02:28 PM, Ben Bacarisse wrote:
> >> jonas.thornvall@gmail.com writes:
> >>
> >>> Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> >>>> <script language="Javascript">
> >> <snip code>
> >>> http://jt.node365.se/BAUTABASE.html
> >>>
> >>> Using the biggest base possible adding "4503599627370495" encoding
> >>> fibonacci in javascript without overflow.
> >>>
> >>> Also fixed ambiguity reading out the numbers in bases over ten by
> >>> using separator for digitplaces. The add can not cause overflow but to
> >>> get rid of base overflow would require some real deep thinking.
> >>>
> >>> The 100000th Fibonacci took 34 seconds i do not think i can get it
> >>> much faster in javascript if your a wizard please prove me wrong.
> >>
> >> I have not tried your code, but I've just written a quick bignum add
> >> function and I can get fib(100000) in about 3.5 seconds.  If I have time
> >> to unravel yours, I'll do a comparative test.  Note that a language with
> >> a good bignum type (Haskell, for example) will do it in less than 100th
> >> of a second.
> >>
> >> Note that your 'challenge' makes it easy to optimise the code.  For
> >> example, using a power of 10 as the base makes the conversion for
> >> printing very simple.
> >>
> >
> > That is well neigh impossible if you used a 10-based decimal since
> > Jonas uses a huge base and is convinced that using a larger base will
> > make computations much faster. Your result would invalidate that
> > claim...
> 
> Using base 10 is quite slow (my code needs 23s for fib(100000) using
> base 10), but I use a higher power of 10 as the base for speed whilst
> keeping printing simple.  With higher powers, you do get faster results
> (up to a limit, of course!).
> 
> -- 
> Ben.

How about using "a real bignumb library" and binary, what will happen?

[toc] | [prev] | [next] | [standalone]

#29229

Fromjonas.thornvall@gmail.com
Date2016-01-11 06:48 -0800
Message-ID<6dac28ba-6ef1-45c4-9d04-48c8c23c2556@googlegroups.com>
In reply to#29227
Den måndag 11 januari 2016 kl. 14:28:20 UTC+1 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
> 
> > Den söndag 10 januari 2016 kl. 14:33:27 UTC+1 skrev jonas.t...@gmail.com:
> >> <script language="Javascript">
> <snip code>
> > http://jt.node365.se/BAUTABASE.html
> >
> > Using the biggest base possible adding "4503599627370495" encoding
> > fibonacci in javascript without overflow.
> >
> > Also fixed ambiguity reading out the numbers in bases over ten by
> > using separator for digitplaces. The add can not cause overflow but to
> > get rid of base overflow would require some real deep thinking.
> >
> > The 100000th Fibonacci took 34 seconds i do not think i can get it
> > much faster in javascript if your a wizard please prove me wrong.
> 
> I have not tried your code, but I've just written a quick bignum add
> function and I can get fib(100000) in about 3.5 seconds.  If I have time
> to unravel yours, I'll do a comparative test.  Note that a language with
> a good bignum type (Haskell, for example) will do it in less than 100th
> of a second.
> 
> Note that your 'challenge' makes it easy to optimise the code.  For
> example, using a power of 10 as the base makes the conversion for
> printing very simple.
> 
> -- 
> Ben.

Yes a bug slipped in so i did get back to old version, those damn javascript arrays so stupid behaviour.
I also get around 3 seconds, and i also check for printouts.
Can you get Fibonacci 1 milling in 360 seconds using base 10?
http://jt.node365.se/fibonacci.html

https://drive.google.com/file/d/0B7yuU1puYuVMSER6dXdEN3NDRUk/view?pref=2&pli=1

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web