Разомнем мозк)

Victor Ananiev · April 1, 2009

Задание довольно увлекательное) нужно посчитать факториал 1 000 000 (факториал 1 000 000 = 1*2*3*4*5*...*999 999*1 000 000). Казалось бы ничего сложного:

var factorial=1;
for(var i=2;i<=1000000;i++)
{
 factorial*=i;
}
//вывод factorial на экран...

Но дело в том что существует Number.MAX_VALUE и округление... Вопрос в том как в 100% точности посчитать такое произведение?

Мои идеи:

Выделить все нолики в конце в отдельную переменную, а числа умножать без них. Результат: числа все равно большие, и округляются.

Множить на следующее число только если результат будет меньше чем Number.MAX_VALUE. Результат: числа округляются, и становятся меньше MAX_VALUE((

Edited April 1, 2009 by Victor Ananiev

homm · April 1, 2009

Если нужна точность — двоично-десятичные числа. Но считаться такое будет, наверное не один год.

zwie · April 1, 2009

в школе помню делал калькулятор на Паскале, который складывал 256-значные числа)

пишем результат в строку и потом по одной цифре забираем из строки, умножаем столбиком и пишем в новую строку

кстати, на форуме все модераторы в честь 1 апреля или как?)

Edited April 1, 2009 by zwie

Jenek · April 1, 2009

Quote
пишем результат в строку и потом по одной цифре забираем из строки, умножаем столбиком и пишем в новую строку

если не ошибся то получается ~6,2 * 10^5 500 000

придется работать со строчками по 5 мегабайт

Victor Ananiev · April 1, 2009

В общем, нужно реализовать умножение и суммирование столбиком)) гг)

rash · April 1, 2009

Victor Ananiev said:
В общем, нужно реализовать умножение и суммирование столбиком)) гг)

Когда разрядность и точность заранее неизвестны, аналогичный способ действительно может использоваться на практике.

Victor Ananiev · April 1, 2009

никогда не думал, что мне придется учить комп считать встолбик)

s0rr0w · April 1, 2009

Victor Ananiev said:
Вопрос в том как в 100% точности посчитать такое произведение?

А математику сюда слабо подключить?

Готовые решения

http://www.luschny.de/math/factorial/index.html

Ну и вот

http://en.wikipedia.org/wiki/Factorial

zwie · April 2, 2009

http://ru.wikipedia.org/wiki/Факториал

там кстати ссылка на калькулятор факториалов. Кто там говорил про 5мегабайтные строки?)

Victor Ananiev · April 2, 2009

the number must be <= 5000 загнулсо он)

http://www.luschny.de/math/factorial/index.html - тут на джаве, а хотелось бы простым скриптом, без компила))

Jenek · April 2, 2009

Quote
там кстати ссылка на калькулятор факториалов. Кто там говорил про 5мегабайтные строки?)

Пятимегабайтные строки это относилось к вычислению в столбик факториала 1 000 000, а не 5000.

А о том, что они пятимегабайтные сказала формула стирлинга, которая, кстати, в википедии и приведена.

zwie · April 2, 2009

упс, количество нулей перепутал)

Victor Ananiev · April 7, 2009

доделал, вот если кому интересно:

код:


<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
 <head>
  <script>
   Number.prototype.isFloat=function()
   {
    return /\./.test(this.toString());
   };
   function add(first, second)
   {
    var sum='';
    var buf=0;
    if(second.toString().length>first.toString().length)
    {
     var temp=first.toString();
     first=second.toString();
     second=temp.toString();
    }
    while(second.toString().length!=first.toString().length)
    {
     second='0'+second.toString();
    }
    while(second.toString().length>0)
    {
     var addr1=first.toString().substring(first.toString().length-1, first.toString().length);
     var addr2=second.toString().substring(second.toString().length-1, second.toString().length);
     var minisum=parseInt(addr1)+parseInt(addr2)+parseInt(buf);
     buf=0;
     if(minisum>9)
     {
      buf=parseInt(minisum.toString().substring(0, minisum.toString().length-1));
      sum=minisum.toString().substring(minisum.toString().length-1, minisum.toString().length).toString()+sum.toString();
     }
     else
     {
      sum=minisum.toString()+sum.toString();
     }
     first=first.toString().substring(0, first.length-1);
     second=second.toString().substring(0, second.length-1);
    }
    if(buf>0)
    {
     sum=buf.toString()+sum.toString();
    }
    return sum.toString();
   }
   function increase(first, second)
   {
    var toSum=new Array();
    var buf=0;
    for(var i='';i.toString().length<first.toString().length;i=i.toString()+'0')
    {
     var incr1=first.toString().substring(first.toString().length-i.toString().length-1, first.toString().length-i.toString().length);
     var res='';
     var insecond=second;
     while(insecond.toString().length>0)
     {
      var incr2=insecond.toString().substring( insecond.toString().length-1, insecond.toString().length);
      var inres=parseInt(incr1)*parseInt(incr2)+parseInt(buf);
      //document.getElementById('uuu').innerHTML+=parseInt(incr1)+' * '+parseInt(incr2)+' + '+parseInt(buf)+' = '+(parseInt(incr1)*parseInt(incr2)+parseInt(buf));
      buf=0;
      if(inres.toString().length>1)
      {
       buf=inres.toString().substring(0, inres.toString().length-1);
       inres=inres.toString().substring(inres.toString().length-1, inres.toString().length);
      }
      res=inres.toString()+res.toString();
      insecond=insecond.toString().substring(0, insecond.toString().length-1);
      //document.getElementById('uuu').innerHTML+=' — buf = '+buf+'<br />';
     }
     toSum[i.length]=(parseInt(buf)>0?buf.toString():'')+res.toString()+i.toString();
     buf=0;
    }
    var result='0';
    for(var j=toSum.length-1;j>=0;j--)
    {
     result=add(result.toString(), toSum[j].toString());
    }
    return result.toString();
   }
   function viewFact(num)
   {
    var regex=/^(.+)(0+)$/;
    var zeros=0;
    var result='1';
    for(var i=2;i<=parseInt(num);i++)
    {
     result=increase(result.toString(), i.toString());
     if(regex.test(result))
     {
      zeros+=result.toString().replace(regex, '$2').length;
      result=result.toString().replace(regex, '$1');
     }
     document.getElementById('uuu').innerHTML=i.toString()+'! = '+result.toString()+' <span style="color:red;">e +'+zeros.toString()+'</span><br />'+document.getElementById('uuu').innerHTML;
    }
   }
   window.onload=function()
   {
    viewFact(1000000);
   }
  </script>
 </head>
 <body>
  <div id="uuu" style="white-space:nowrap;line-height:20px;background-color:#eef;"></div>
 </body>
</html>

или скачать:

http://upload.com.ua/get/900790588/

http://rapidshare.com/files/218195283/factorial.rar

Victor Ananiev · April 7, 2009

На четырех ядрах считает до 300 за сутки)

ZoNT · April 8, 2009

Victor Ananiev said:
На четырех ядрах считает до 300 за сутки)

zwie · April 8, 2009

а до 301 еще неделю?

Victor Ananiev · April 8, 2009

за то считает))))) у кого то есть другие предложения?

Edited April 8, 2009 by Victor Ananiev

ZoNT · April 8, 2009

У мня есть предложение: сделай лучше нормаьный кроссбраузерный редактор типа tinyMCE, только безглючный и маленький...

zwie · April 9, 2009

такую задачу все-таки лучше переложить на сервер наверное =) и посмотреть алгоритмы, может быстрее можно, в английской вики же было что-то.

1,000,000! = 8.2639316883... × 10^5565708 вот ответ в конце концов)

Victor Ananiev · April 9, 2009

мне точный нужен, а вики считай по формуле, а она не совсем точная) а на сервере таймаут 30 сек для цикла, знаю что можно покопать httpd config & phpini но все таки не думаю что выиграю на этом много)

Sign In

Разомнем мозк)

Question

Link to comment

Share on other sites

19 answers to this question

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Обсуждения

Important Information