Silnia dużej liczby

Question

nk jak oblcizyc silnie z miliona zeby program sie nie runował przez 2 minuty

Comments

Może słyszałeś o czymś takim jak przetwarzanie równoległe?
Jeśli chcesz to obliczać na urządzeniu, którego procesor ma wiele wątków to polecam :)

Edit: Jeżeli byś już robił to polecam program odpalać z wykorzystaniem:
(Możliwa ilość wątków - 1), bo jeśli to urządzenia ma interfejs graficzny to się może nieźle ściąć :D

---

Może słyszałeś o czymś takim jak przetwarzanie równoległe?

Współbieżność/równoległość nic tu nie pomoże. Dla żadnego współczesnego procesora nie jest problemem wykonać milion mnożeń czy to stało- czy zmiennoprzecinkowych w pomijalnym czasie. Problemem jest ilość pamięci.

Silni z miliona nie policzysz nawet gdybyś symulował obliczenia korzystając ze stringów. Wynikowy string nie zmieści ci się w pamięci. Chyba, że opracujesz jakiś swój sposób zapisu liczb :P

---

Czy ja wiem... właśnie sprawdziłem naiwną implementację. Dla 8 wątków z użyciem biblioteki GMP liczy się 15 sek. Jakoś tego specjalnie nie optymalizowałem.

---

Właśnie też mi się wydawało, ludzkość jakoś liczy większe rzeczy niż silnie z miliona i problemem nie jest właśnie ilość pamięci , a czas obliczeń

---

Liczba wynikowa ma 5565709 cyfr czyli ~ 5.5 MB. Raczej się zmieści w RAM.

Wersja prosta dla jednego wątku może wyglądać tak:

(C99)

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

size_t mpz_out_str (FILE *, int, const mpz_t);

void factorial(int n){
  mpz_t value;

  mpz_init_set_ui(value, 1);

  for (int i = 1; mpz_mul_ui(value, value, i), i <= n ; ++i) {}

  mpz_out_str(stdout, 10, value);
  putchar('\n');
  mpz_clear(value);
}

int main(void){
  int n = 1000000;

  assert( n >= 0);
  factorial(n);

  return EXIT_SUCCESS;
}

Liczy się (oczywiście w zależności od mocy obliczeniowej danego CPU) około 1.5-2 min.

Wielowątkowo trochę mniej czytelny kod. (dodam w wolnej chwili bo mam poza swoim komputerem).

---

Oh, to przepraszam za wprowadzenie w błąd

---

@mokrowski, Dzięki, aż w siebie zwątpiłem kiedy VIP napisał , że się nie da :D

---

Przepraszam XD nie powinno być tych tytułów punktowych

---

No .. i jak do tego choć trochę przysiąść to i wyniki lepsze :-) 3.5 sekundy na 8 rdzeniach.

#include <gmpxx.h>
#include <iostream>
#include <vector>
#include <thread>
#include <future>

mpz_class factorial_worker(int start, int end) {
    mpz_class result{1};
    for(auto i = start; i <= end; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    int n = 1000000;
    unsigned cpu_cores = std::thread::hardware_concurrency();
    // TODO: dodanie kalkulacji jeżeli n / cpu_cores nie jest całkowite.
    int chunk = n / cpu_cores;

    // map... 
    std::vector<std::future<mpz_class>> partial_results;
    partial_results.reserve(cpu_cores);

    for(auto i = 0; i < cpu_cores; ++i) {
        partial_results.emplace_back(
                std::async(std::launch::async, factorial_worker, i * chunk + 1, (i + 1) * chunk)
        );
    }

    // reduce...
    mpz_class result{1};
    for(auto& p: partial_results) {
        result *= p.get();
    }
    std::cout << result << '\n';
}

 

Answer 1

Przykro mi, ale nawet jeśli zaczniesz operować na string'ach to nie obliczysz silni z miliona :).

Jeśli chcesz przyspieszyć pracę takiego programu to poszukaj A) gotowych bibliotek obsługujących lepsze algorytmy do obliczania silni B) sam przejrzyj np. wikipedie w poszukiwaniu takowych i zaimplementuj samemu w C++.

Chyba nie zdajesz sobie sprawy ze złożoności obliczenia silni z miliona 

Comments

dzięki

i zdaje sobie sprawę jak to ogromna i trudna do obliczenia liczba,

---

Jasne, że to da się zrobić. Np w pythonie int nie ma ograniczeń:

from math import factorial
print(factorial(1000000))

Pomieli dosyć dlugo a liczba prawdopodobnie nie zmiesci się w konsoli xD ale policzy.

Answer 2

Da się to zrobić, ale ze względu na złożoność wynikającą z obsługi wielgachnych integerów szybko się to nie policzy.

Potrzebujesz więc jedynie dobrej biblioteki obsługującej duze integery, która w pythonie od wersji 3 jest po cichu wbudowana w normalnego inta i nie ma on ograniczeń, dlatego w najbardziej pytonicznym stylu:

from solutions import solution
print(solution())

Twój problem wygląda tak:

from math import factorial
print(factorial(1_000_000))

Co prawda liczyło sie dobre pare minut i liczba nie zmiesciła się w konsoli, ale policzył :D.

W przypadku innych języków prawdopodobnie będziesz potrzebował jakiejś zewnętrznej biblioteki do obsługi dużych integerów.

Answer 3

z tym nk chodzi o symbol Newtona? Czy pytasz po prostu o 1000000! ???

Bo jeśli o newtona to tutaj masz przykład rekurencji która dosyć sprawnie skraca ze sobą liczby podczas liczenia

unsigned long long Newton(unsigned n, unsigned k) {
    if (n == k || k == 0) return 1;
    return Newton(n - 1, k - 1) * n / k;
}

 

Comments

nk to po prostu niech ktoś

---

aa okej :D to w takim razie nie wiem czy jest jakiś sposób na obliczenie tak dużej liczby.