pekfos |
» 2017-11-03 21:58:54 pot_szybkie( a, n / 2 ) * pot_szybkie( a, n / 2 )
|
Poważnie? Przypomnij, po co chcesz coś tu optymalizować, skoro twoje szybkie potęgowanie jest rząd wielkości wolniejsze niż powinno? |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-11-03 22:22:45 Taka zmiana pomoże? template < typename M >
M pot_szybkie( M a, unsigned int n )
{
if( n % 2 == 1 ) return a * pot_szybkie( a, n - 1 );
else
{
Matrix_2x2 pol = pot_szybkie( a, n / 2 );
return( pol * pol );
}
|
|
mateczek |
» 2017-11-04 08:59:51 rozumiem iż Monika90 miała rację i źle podałeś treść zadania ?? podałeś (1 ≤ n,m ≤ 109) a powinno być (1 ≤ n,m ≤ 10^9)?? 2 chcesz obliczyć 'n' elementy ciągu korzystając z właściwości macierzy |1 1|^n |1 0| 3 zdajesz sobie sprawę iż szablony czy funkcje nie działają magicznie??. i szablon nie sprawi iż z automatu program zadział gdy natrafi na działanie (macierz%int) czy (int * macierz)!!! 4 zdajesz sobie sprawę iż w c++(korzystając ze standardowych typów danych) ostatnim elementem ciągu jaki jesteś w stanie policzyć to fib(94) Tym samym nie policzysz nic więcej poza |1 1|^94 |1 0| 5 masz policzyć fib(n)%m czy wzory które znalazłeś dla liczb (szybkie potęgowanie modularne) będą prawdziwe dla macierzy ?? czy to są te wzory które potrzebujesz?? nie wiem nie sprawdzałem. Komputer Ci nie wykona z automatu działania A%m jeśli "A" to macierz 6 rekurencyjne algorytmy są z reguły wolne. poniższy to już mistrzostwo świata dodanie 42 liczb i dobre 10s na moim pc #include<iostream>
using namespace std;
unsigned long long fib( int a )
{
if( a == 0 ) return 0;
if( a == 1 ) return 1;
else if( a > 1 )
{
return fib( a - 1 ) + fib( a - 2 );
}
}
int main() {
cout << fib( 42
);
}
[ cpp ]
|
|
garlonicon |
» 2017-11-04 11:48:42 Dlaczego operacja pomnożenia dwóch macierzy miałaby być szybsza, niż zwykłe dodawanie i odejmowanie dwóch zmiennych? Korzystając z macierzy trzymasz cztery zmienne, z czego dwie odnoszą się do tego samego wyrazu ciągu fibonacciego. Może lepiej kombinuj ze zwykłymi zmiennymi. Załóżmy, że masz dwa kolejne wyrazy ciągu fibonacciego oraz że obie wartości są mniejsze od m . Aby otrzymać dwie kolejne wartości, wystarczy napisać: int a = 0, b = 1;
a += b;
if( a >= m ) a -= m;
b += a;
if( b >= m ) b -= m; Dwa dodawania, dwa odejmowania i dwa wyrażenia warunkowe. Wątpię, aby macierze cokolwiek tutaj przyspieszyły. Poza tym, korzystając z powyższego algorytmu uzyskujesz dwie wartości naraz i nie potrzebujesz żadnych zmiennych pomocniczych. |
|
mateczek |
» 2017-11-04 12:19:12 pewnie chodzi o takie działanie które obniża ilość iteracji dla wielkich wykładników
x^16 normalnie 16 operacji
ale można w trzy operacje
y=x*x;
z=y*y;
wynik=z*z;
Ale nie wiem jak tam w te macierze modulo wkręcić. |
|
jankowalski25 |
» 2017-11-04 14:27:45 Dobra, spróbuję z macierzami. Przechowujesz w niej trzy kolejne wartości ciągu fibonacciego, więc wystarczą trzy zmienne zamiast czterech. Na razie udało mi się podnieść taką macierz do kwadratu korzystając z dwóch zmiennych pomocniczych, ale pewnie da się prościej. int a = 0, b = 1, c = 1;
int d = a + c;
int e = b * b;
a *= a;
c *= c;
a += e;
c += e;
b += d; W ten sposób w zmiennej b znajdzie się dwa razy dalszy wyraz ciągu fibonacciego, czyli na przykład dla: a = fib( 7 );
b = fib( 8 );
c = fib( 9 ); wynikiem końcowym będzie: a = fib( 15 );
b = fib( 16 );
c = fib( 17 ); Takie coś działa na pewno jeśli b jest 2 n-tym wyrazem ciągu fibonacciego. W pozostałych przypadkach to będzie prawda, jeśli poniższe wyrażenie będzie prawdziwe: ( fib( 2 * n - 1 ) == fib( n - 1 ) * fib( n - 1 ) + fib( n ) * fib( n ) ) &&
( fib( 2 * n ) == fib( n ) *( fib( n - 1 ) + fib( n + 1 ) ) ) &&
( fib( 2 * n + 1 ) == fib( n + 1 ) * fib( n + 1 ) + fib( n ) * fib( n ) ) Możliwe, że to zawsze wynosi true , jeszcze nie rozpisałem tego matematycznie na kartce. Niestety, nadal nie mam pomysłu, jak dołożyć tutaj modulo, żeby to było względnie szybkie. |
|
Luq |
» 2017-11-04 15:53:49 #include <iostream>
#include <cstring>
struct Matrix2x2 {
int nums[ 2 ][ 2 ];
Matrix2x2() {
std::memset( nums, 0, sizeof( nums ) );
}
};
Matrix2x2 MultiplyWithMod( const Matrix2x2 & one, const Matrix2x2 & two, int mod ) {
Matrix2x2 result;
for( int i = 0; i < 2; ++i ) {
for( int j = 0; j < 2; ++j ) {
for( int k = 0; k < 2; ++k ) {
result.nums[ i ][ j ] += one.nums[ i ][ k ] * two.nums[ k ][ j ];
}
result.nums[ i ][ j ] %= mod;
}
}
return result;
}
Matrix2x2 FastMatrixPowWithMod( const Matrix2x2 & mat, int power, int mod ) {
if( power < 2 )
return mat;
Matrix2x2 half = FastMatrixPowWithMod( mat, power / 2, mod );
if( power % 2 == 0 )
return MultiplyWithMod( half, half, mod );
else
return MultiplyWithMod( half, MultiplyWithMod( half, mat, mod ), mod );
}
int main() {
std::cout << 2880067194370816120 % 83 << '\n';
Matrix2x2 mat;
mat.nums[ 0 ][ 0 ] = mat.nums[ 0 ][ 1 ] = mat.nums[ 1 ][ 0 ] = 1;
std::cout << FastMatrixPowWithMod( mat, 89, 83 ).nums[ 0 ][ 0 ] << '\n';
}
Myślę, że coś w tym stylu powinno przejść. |
|
mateczek |
» 2017-11-04 20:11:02 @luk. spoko powinno grać. Ja nie wiedziałem jak się zachowa mnożenie macierzy gdy wyciągnie się Modulo z każdego elementu po wymnożeniu. Ale wydaje się działać :) |
|
| 1 2 3 4 5 « 6 » 7 |