Silnia

Odpowiedz Nowy wątek
2019-11-08 17:49
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ć odrazu wynik a nie mnożyć w pętli tyle kolejnych liczb.

Pozostało 580 znaków

2019-11-08 18:08
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^^

Pozostało 580 znaków

2019-11-08 18:13
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ś. 🤣

Pozostało 580 znaków

2019-11-08 18:24
0

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

edytowany 1x, ostatnio: Rebus, 2019-11-08 18:28

Pozostało 580 znaków

2019-11-08 18:30
0

Jest i taka opcja https://stackoverflow.com/que[...]2879/factorial-using-addition

Która odpowiedź jest związana z pytaniem OP'a? - lion137 2019-11-08 19:03
Na moje ślepe oko nr 2. Chciał silnię inaczej niż przez mnożenie, to niech ma silnię przez dodawanie. Nie wątpię w istnienie innych metod. - Serechiel 2019-11-08 19:51

Pozostało 580 znaków

2019-11-08 18:33
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.

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2019-11-08 18:34
Pokaż pozostałe 5 komentarzy
Jeśli zamierzasz przetworzyć liczby większe od sqrt(n), to tracisz jedyną przewagę pomysłu, bo tracisz subliniowość algorytmu. - enedil 2019-11-13 14:48
Sito potrzebuję liczyć do sqrt(N) natomiast podzielniki - wszystkie pierwsze z zakresu - _13th_Dragon 2019-11-13 19:48
Sito, które przetwarza elementy do sqrt(N), ale odsiewa aż do N, przynajmniej raz przetworzy każdą niepierwszą liczbę z zakresu sqrt(N) do N, a takich jest asymptotycznie N - sqrt(n) - log(N) + log(sqrt(n)) = O(n). - enedil 2019-11-13 22:37
Przy silni z dużej liczby i tak nas ubije mnożenie wielotysięczno cyfrowych liczb (do liczb ok. 40 tys. cyfrowych ~nlogn), potem Schönhage–Strassen algorithm, powiedzmy ~n. - lion137 2019-11-13 23:02

Pozostało 580 znaków

2019-11-08 19:01
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.


Każdy programista przybywający z innego miasta jest fachowcem.

Pozostało 580 znaków

2019-11-08 19:32
0

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


Nie zupełnie, widziałeś ile zer na końcu 100! ? zaś mnożenia 2-jek i 5-tek da się zrobić w czasie O(log(n)) - _13th_Dragon 2019-11-09 00:31

Pozostało 580 znaków

2019-11-08 21:02
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

Pokaż pozostałe 12 komentarzy
@Patryk27u @gk1982owi chodzi o memoization. - WeiXiao 2019-11-09 01:03
@WeiXiao: memoizacja tutaj nie pomaga, gdyż jest tylko jedno wywołanie rekurencyjne. Wszystko co zmieniasz tym, to złożoność pamięciową z log(n!) na sum(log(i!) for i in range(n)) - enedil 2019-11-09 01:11
@enedil: dlaczego nie? licząc 4! lecisz od tyłu 4 * sprawdzasz czy masz już 3!, jeżeli tak to zwracasz "do góry" 6. nie łapie czegoś :P - WeiXiao 2019-11-09 01:19
ah, dobra. Jedno wyliczenie x!, a nie kilka, ok :D - WeiXiao 2019-11-09 01:21

Pozostało 580 znaków

2019-11-08 22:52
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

Pozostało 580 znaków

2019-11-08 23:01
0

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


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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

Robot: CCBot (2x)