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.
0
1
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^^
0
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ś. 
0
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ś
0
Jest i taka opcja https://stackoverflow.com/questions/55082879/factorial-using-addition
1
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.
2
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.
0
Jeśli nie, jak wyżej (aproksymacja), to Musisz wykonać nmnożeń, nie da się od tego uciec.
0
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
0
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
0
Tak czy siak, wynik z mnożenia dużych liczb Będziesz miał w pamięci.
1
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.
0
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
1
1
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
1
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ć)
0
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?
0
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;
}