Silnia

0

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.

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ś

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

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;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1