Tak mniej wiecej z 3mln. Nie zmiesci sie to w long double (c). Macie jakies pomysły, jak to wykonać?
0
0
A przypadkiem nie potrzebujesz tylko ostatnich dwóch znaków?
0
Nie. Potrzebuje całości. Ale jeśli znasz algorytm liczenia n-tego znaku, to sprawa rozwiązana.
0
Zróbmy tutaj ciekawy eksperyment myślowy:
Korzystając z przybliżonego wzoru Sztirlinga możemy wydedukować że log2(n!) czyli de facto liczba bitów potrzebnych do zapisania liczby n! wynosi:
1/2 log(2pin/e) + nlog(n/e)
ergo dla n = 3000000 mamy
1/2 log(6931568) + 3000000log(1103753) = 11 + 300000020 ~= 60 000 000 bitów czyli 7500000 bajtów czyli 7,15 MB
Czyli samo ZAPISANIE twojej liczby binarnie wymagałoby 7,15 MB pamięci.
Gdybyś postanowił zaimplementować to na bazie operacji pisemnych to oczywiście byłoby trochę gorzej bo wtedy potrzebowałbyś log10(n!) bajtów do zapisania takiej liczby czyli:
1/2 * 7 + 3000000*7 ~=21 000 000 bajtów czyli 20,027 MB na samo zapisanie w pamięci komputera liczby n! dla n=3mln
0
Jedyne zajęcia, jakie posiadam w klasie maturalnej to "matematyka". Taka zwykła. A plik wynikowy silni z 3mln ma 18mb, więc coś pokręciłes. Posiadam ten plik.
1
No @Shalom mocno pokręcił. 60 megabitów to ponad 7 gibibajtów? :D
Silnia z 3mln rzeczywiście ma nieco więcej niż 18mln cyft w zapisie dziesiętnym: http://www.wolframalpha.com/input/?i=3000000%21
Możesz więc spokojnie mnożyć pisemnie, choć to dość długo potrwa. Ale są pewne triki, np duże silnie mają bardzo dużo końcowych zer, więc można wstępnie oszacować czy n-ta cyfra jest zerem.
0
Oczywiście pomyliłem sobie GB i MB ;) Reszta obliczeń jest poprawna, ale wzory przybliżone stąd trochę rozbieżności (18 a 20 MB).
Niemniej jednak wcale nie ułatwia to sprawy bo wykonywanie obliczeń na takich dużych liczbach trochę czasu zajmie...
0
Powiedziałbym, ze można obliczyć (dokładnie) ile jest zer na końcu. Jak mnożymy *10, *20, 52 itd
0
No tak. Dokładnie to trzeba policzyć ile będzie piątek i dwójek w rozkładzie na czynniki każdej kolejnej liczby, zsumować wykładniki i wziąć minimum (z tych dwóch wykładników). Można też to zrobić sprytniej.
Dodatkowo policzenie ostatniej niezerowej cyfry też jest względnie łatwe.
0
Po co Ci może być taka liczba. (1e6)! to jest około 8.26e5565708, twoja liczba jest 3 razy większa.
Wiek wszechświata w joktosekundach: 4.254e41
Liczba atomów w obserwowalnym wszechświecie: 1e78 - 1e82. Nawet jeżeli dodać do tego wszystkie inne cząstki elementarne to będzie 2.5e89. Nawet jeżeli te liczby są super niedokładne, to więcej niż 1e100 nie będzie. (1e100 to jest około 70!)
(źródło: Internety ;-)
Ta Twoja liczba jest tak nieprawdopodobnie wielka, że na pewno jest Ci niepotrzebna.
0
Chce ją policzyć tylko po to, zeby... ją miec ;p To dość ciekawy problem napisać program liczący tak duże silnie. Oczywiscie to mi niepotrzebne, bo po co niby.
Co do tej liczby zer: trzeba zliczyc liczby typu 10, 20... i liczby typu parzysta*5. Co do tego drugiego, to wystarczy policzyć ilość liczb typu 5, 15, 25... bo parzystych będzie zawsze więcej niż tych z 5 na końcu, wiec sie "dopełni".
Czyli wynik=a/10 + a/5. Dobrze myślę?
0
Na załączonym przeze mnie linku do WolframAlpha jest podana dokładna liczba końcowych zer. I nie zgadza się z twoim wzorem :]
0
@Wibowit: Co masz na myśli pisząc "Można też to zrobić sprytniej" ?
0
Podrzucam kod w Javie do liczenia silnii z 3000000. Niestety w C implementację BigIntegera musisz zaklepać sobie sam :]
Program wykonuje się u mnie jakieś półtorej minuty. Na typowym kompie to będzie pewnie kilka minut. A wersja 'naiwna', tzn ta zakomentowana, to pewnie całą wieczność :P
PS. nie wiem czy zastosowane optymalizacje mają sens. Po prostu chciałem zaszpanować moją Karatsubą :P
PS. a i wyświetlam tylko długość co by nie zawalać konsoli.
Edit: a w sumie ta Karatsuba to nie moja. Pomyliło mi się :P Źródło tutaj: http://introcs.cs.princeton.edu/java/78crypto/Karatsuba.java
package javaapplication1;
import java.math.BigInteger;
public class JavaApplication1 {
public static void main(String[] args) {
//System.out.println(factorial(3000000).bitLength());
System.out.println(partialFactorial(BigInteger.ONE,
BigInteger.valueOf(3000000)).bitLength());
}
private static BigInteger factorial(int number) {
BigInteger result = BigInteger.ONE;
for (int i = 1; i <= number; i++) {
result = BigInteger.valueOf(i).multiply(result);
}
return result;
}
private static BigInteger partialFactorial(BigInteger a, BigInteger b) {
if (a.equals(b)) {
return a;
} else {
BigInteger middle = a.add(b).shiftRight(1);
return karatsuba(partialFactorial(a, middle),
partialFactorial(middle.add(BigInteger.ONE), b));
}
}
private static BigInteger karatsuba(BigInteger x, BigInteger y) {
// cutoff to brute force
int N = Math.max(x.bitLength(), y.bitLength());
if (N <= 2000) {
return x.multiply(y); // optimize this parameter
}
// number of bits divided by 2, rounded up
N = (N / 2) + (N % 2);
// x = a + 2^N b, y = c + 2^N d
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
BigInteger d = y.shiftRight(N);
BigInteger c = y.subtract(d.shiftLeft(N));
// compute sub-expressions
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger abcd = karatsuba(a.add(b), c.add(d));
return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N))
.add(bd.shiftLeft(2 * N));
}
}
0
Mógłby mi to ktoś na pseudokod przetłmaczyć? Niby podobienstwo składniowe c++ do javy jest spore, ale jakoś tego nie rozumiem.
1
Algorytm Karatsuby jest wytłumaczony tutaj: http://pl.wikipedia.org/wiki/Algorytm_Karacuby
A reszta powinna być prosta do ogarnięcia.
0
Jakby kogoś interesowało: algorytm do liczenia ilości końcowych zer w liczbie a!
#include <math.h>
licznik log(typ a, typ x)
{
licznik wynik=0;
typ A=a;
while(a<=x)
{
a*=A;
wynik++;
}
return wynik;
}
licznik liczba_zer(typ a)
{
licznik wynik=0;
for(licznik k=1; k<=log(5, a); ++k)
wynik+=a/(pow(5, k));
return wynik;
}
2
Koszmar!
licznik Liczba_Zer(typ a)
{
licznik wynik=0;
while(a) wynik+=(a/=5);
return wynik;
}
0
Wibowit napisał(a):
Podrzucam kod w Javie do liczenia silnii z 3000000. Niestety w C implementację BigIntegera musisz zaklepać sobie sam :]
Program wykonuje się u mnie jakieś półtorej minuty. Na typowym kompie to będzie pewnie kilka minut. A wersja 'naiwna', tzn ta zakomentowana, to pewnie całą wieczność :P
Skoro już jesteśmy przy innych implementacjach, daję Pythona:
import gmpy,datetime
d1=datetime.datetime.now()
gmpy.fac(3000000)
print datetime.datetime.now()-d1
U mnie się wykonuje w 003.779855 :P
0
Twoje rozwiązanie to wywołanie funkcji z GMPlib, a moje to czysta Java ;]
GMPliba równie dobrze można by wywołać z dowolnego innego języka, także z Javy. Nie byłoby wtedy co porównywać.
0
A czy java.math.BigInteger zostało napisane w Javie, czy w C++?
BTW. zapisanie wyniku do pliku tekstowego ma 18MB (piszę tak dla potwierdzenia).
0
W czystej Javie: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/math/BigInteger.java?av=f
Mnożenie w BigIntegerze jest robione dość naiwnym, a co za tym idzie powolnym algorytmem. GMPlib jest zapewne super zoptymalizowane, do tego pewnie factorial też jakoś tam sprytnie liczy tą silnię, a nie tak jak ja (w końcu nie myślałem nad tym godzinami).
0
Jak implementacje w różnych językach liczenia silni to:
factorial :: Num a => a -> a
-- factorial n = product [1..n]
factorial = product . enumFromTo 1 -- pointless bardziej mi się podoba
main :: IO ()
main = putStrLn . show $ factorial 3000000
puts (1..3_000_000).reduce(:*)
(display (fold-left * 1 (iota 3000000 1))
0
Próbowałem wymyślić sprytniejszy algorytm do liczenia silnii, ale wymiękłem. Oto kod:
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class SmartFactorial {
static final int Limit = 3000000;
static final boolean[] sieve = new boolean[Limit + 1];
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
Arrays.fill(sieve, true);
sieve[0] = sieve[1] = false;
for (int i = 2; i <= Limit; i++) {
for (int j = i * 2; j <= Limit; j += i) {
sieve[j] = false;
}
}
Queue<BigInteger> numbers = new PriorityQueue<>(
(int) (2 * Limit / Math.log(Limit)),
new Comparator<BigInteger>() {
@Override
public int compare(BigInteger o1, BigInteger o2) {
return o1.bitLength() - o2.bitLength();
}
});
for (int i = 0; i < sieve.length; i++) {
if (sieve[i]) {
int counter = 0;
for (long j = i; j <= Limit; j *= i) {
counter += Limit / j;
}
numbers.add(pow(BigInteger.valueOf(i), counter));
}
}
while (numbers.size() >= 2) {
if (numbers.size() == 10 || numbers.size() == 100) {
System.out.println((numbers.size() - 1)
+ " multiplications left. Current time: "
+ (System.currentTimeMillis() - startTime));
}
numbers.add(karatsuba(numbers.remove(), numbers.remove()));
}
System.out.println(numbers.peek().bitLength());
System.out.println("End time: "
+ (System.currentTimeMillis() - startTime));
}
private static BigInteger pow(BigInteger number, int exponent) {
if (exponent == 0) {
return BigInteger.ONE;
}
if (exponent == 1) {
return number;
}
BigInteger result = BigInteger.ONE;
BigInteger pow2k = number;
int mask = 1;
while (mask <= exponent) {
if ((mask & exponent) != 0) {
result = karatsuba(result, pow2k);
}
mask *= 2;
if (mask > exponent) {
break;
}
pow2k = karatsuba(pow2k, pow2k);
}
return result;
}
private static BigInteger karatsuba(BigInteger x, BigInteger y) {
// cutoff to brute force
int N = Math.max(x.bitLength(), y.bitLength());
if (N <= 2000) {
return x.multiply(y); // optimize this parameter
}
// number of bits divided by 2, rounded up
N = (N / 2) + (N % 2);
// x = a + 2^N b, y = c + 2^N d
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
BigInteger d = y.shiftRight(N);
BigInteger c = y.subtract(d.shiftLeft(N));
// compute sub-expressions
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger abcd = karatsuba(a.add(b), c.add(d));
return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N))
.add(bd.shiftLeft(2 * N));
}
}
Wąskim gardłem jest moim zdaniem procedura mnożenia. Karatsuba do demonów wydajności nie należy, a Toom-Cooka czy Shonage-Strassena nie chce mi się implementować/ szukać/ przerabiać gotowce/ etc Myślę, że po implementacji Toom-Cooka i Shonage-Strassena czas zszedłby do max kilkunastu sekund sumarycznie na moim kompie. A tak to dostaję takie logi:
run:
99 multiplications left. Current time: 5023
9 multiplications left. Current time: 19792
60221521
End time: 85951
BUILD SUCCESSFUL (total time: 1 minute 27 seconds)
Z czego wynika, że ponad 75% czasu jest zjadane przez ostatnie 9 mnożeń.
W rozwiązaniu użyłem kolejki priorytetowej, by zawsze mnożyć parę najkrótszych liczb, ale nie zmierzyłem jaki to ma dokładnie wpływ na wydajność.
GMPlib zapewne używa rozszerzeń SIMD i bawi się z niskopoziomowymi optymalizacjami, więc ciężko będzie osiągnąć taką wydajność z poziomu czystej Javy (w zasadzie to obecnie prawdopodobnie niemożliwe).
0
http://ideone.com/eK3jaU
moja implementacja w C++