Silnia

Silnia
Witam czy jest jakaś opcja rozwiązać problem silni inaczej niż mnożyć liczba za liczbą np. nie wiem coś do kwadratu razy coś do sześcianu razy coś do którejś tam i mieć Od razu wynik a nie mnożyć w pętli tyle kolejnych liczb.

Rebus napisał(a):

Witam czy jest jakaś opcja rozwiązać problem silni inaczej niż mnożyć liczba za liczbą

Rebus napisał(a):

nie wiem coś do kwadratu razy coś do sześcianu razy coś do którejś tam

Ale to nadal mnożenie xD

PS: możesz użyć rekurencji, ale też nadal to mnożenie będzie^^

No tak ale potrzebuje do dużych liczb jak mam mieć duże paro gigabajtowe wyniki to wolałbym metodę na skrótu. Trzeba ogarnąć jakieś wzory skróconego wielokrotnego mnożenia czy coś.

Nawet jakby było to skomplikowane zawiłe to bym to jakoś ogarnął ale czy coś takiego jest w ogóle byleby dawało dobry wynik a nie jakiś przybliżony czy coś

Jest i taka opcja https://stackoverflow.com/questions/55082879/factorial-using-addition

Mam pomysł ale trza sprawdzić czy zadziała, to znaczy zadziała na 100% ale czy będzie szybszy ...:

• Szukasz liczb pierwszych nie większych niż sqrt(N)
• Zliczasz pierwsze dzielniki liczby N
• Metodą szybkiego potęgowania zliczasz 2^x, 3^y, 5^z itd
• Mnożysz wyniki.

Po to wymyślili komputery żeby takie obliczenia wykonywały a nie matematycy na kartkach czy tablicy. Jak nie podoba Ci się przybliżony wzór Stirlinga to wymyśl coś lepszego niż komputer lub matematyk.

Jeśli nie, jak wyżej (aproksymacja), to Musisz wykonać nmnożeń, nie da się od tego uciec.

Stablicuj wyniki i wrzuć je sobie do cache'a. Ogólnie to trochę mnie dziwi, że nikt nie zwrócił uwagi na najpoważniejszy problem z silnia czyli bardzo szybkie przekraczanie zakresu zmiennych

korzystam big intiger mpz_class ogranicza mnie ram. Z sumą jest prosto ostatni wyraz np powiedzmy 5 razy (5+1)/2. suma liczb od 1 do 5. z mnożeniem jest trudniej

Tak czy siak, wynik z mnożenia dużych liczb Będziesz miał w pamięci.

OPa pewnie tak interesuje kilka ostatnich cyfr z wyniku, bo tyle było podane w zadaniu, a w takim przypadku liczenie całej silni nie ma zupełnie sensu.

tak na chwile potrzebuję do działań pewnych potem następny przedział np od 1001 do 2000 i tak dalej myślałem nawet że jak znam liczbę silni do x to łatwo oszacuję pomnożone liczby od x+1 do 2x. a tu to łatwo widzę nie jest jak się wydaje

Da się trochę szybciej niż mnożąc po kolei.

https://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication
https://pdfs.semanticscholar.org/7388/ef8a3fa31b2d01f2835b3beeccdb16c0616a.pdf

Witam!
Udało mi się coś wykombinować jeśli chodzi o szybkość wyliczenia silni. Jeśli kogoś to zainteresuje to jest możliwość mnożenia połowy tylko liczb jadąc innym ciągiem czyli czas będzie skrócony o blisko połowę. Więc jak to zrobić. Najlepiej będzie jak liczba z której będziemy chcieli wyliczyć silnie będzie nieparzysta. W przypadku parzystej nie ma oczywiście tragedii trzeba będzie tą ostatnią po prostu domnożyć na końcu. Musimy wyznaczyć liczbę która leży po środku czyli taką która po prawo i po lewo ma tyle samo liczb np. 1,2,3,4,5,6,7 czyli 4. podnosimy 4 do kwadratu i odejmujemy jeden i ta liczba to pierwsza liczba do kolejnego mnożenia potem odejmujemy od niej dwa większą czyli trzy i znowu ją mnożymy czyli można to zapisać tak (16-1)*(15-3)*(12-5) razy jeszcze ta środkowa liczba 4. a tego -1,-3,-5... będzie zawsze tylko tyle ile jest liczb po lewej bądź prawej stronie tej w tym przypadku czwórki czyli najprościej 4-1. Nie wiem czy czegoś za bardzo nie zamotałem ale jak coś piszcie co o tym sądzicie.

mój kod c++ :

#include<gmpxx.h>
#include<gmp.h>
#include<iostream>
using namespace std;

int main()
{mpz_class a,b=1,c,d,e,f,g=1;
cout<<"podaj liczbę z której chcesz wyliczyć silnię: ";
cin>>a;if(a%2==0){b=a;c=a/2;d=c-1;}else{c=a/2;d=c;c++;}
f=c*b;c*=c;
for(e=0;e<d;e++)
{c-=g;f*=c;g+=2;}
cout<<endl<<f<<endl;
//cout<<endl<<"Koniec!"<<endl;
return 0;}

na linux trzeba doinstalować: sudo apt-get install libgmp-dev
i skompilować poleceniem: g++ -Wall -std=c++11 plik.cpp -lgmpxx -lgmp

Trochę bez sensu. Jak już i tak bierzesz GMP to czemu nie użyć https://gmplib.org/manual/Factorial-Algorithm.html ? :) (co zresztą implementuje ten sam algorytm który opisałeś wyżej. I troche wątpie że Udało mi się coś wykombinować, tylko po prostu przeczytałeś jak to zrobić)

To co w tym linku to ten sam sposób co mój? Ja to wymyśliłem wczoraj czyli już jest taka funkcja jak to się stosuje w GMP?

Twój kod z wcięciami (w stylu LLVM):

#include <gmpxx.h>
#include <gmp.h>
#include <iostream>
using namespace std;

int main() {
  mpz_class a, b = 1, c, d, e, f, g = 1;
  cout << "podaj liczbę z której chcesz wyliczyć silnię: ";
  cin >> a;
  if (a % 2 == 0) {
    b = a;
    c = a / 2;
    d = c - 1;
  } else {
    c = a / 2;
    d = c;
    c++;
  }
  f = c * b;
  c *= c;
  for (e = 0; e < d; e++) {
    c -= g;
    f *= c;
    g += 2;
  }
  cout << endl << f << endl;
  // cout << endl << "Koniec!" << endl;
  return 0;
}