Wg stanu na dzień dzisiejszy największa znana liczba pierwsza to 2^282589933 − 1. Oczywiście można znaleźć w necie plik z zapisem blisko 25 milionów jej cyfr, ale byłoby to pójście na łatwiznę.
Ma ktoś pomysł jak wyznaczyć te 25 mln cyfr z pomocą komputera?
0
0
lubie_programowac napisał(a):
Na szybko - teoria: https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html + https://www.rookieslab.com/posts/fast-power-algorithm-exponentiation-by-squaring-cpp-python-implementation
Kolega zniszczył mnie po całości.
Program w C który sobie napisałem wyznaczył 2 do 82585933 w 11 godzin. Program napisany wg. wskazówki kolegi (co zajęło mi raptem 5 minut) potrzebował na to aż... 3 minuty i 7sekund na relatywnie kiepskim komputerze z innymi taskami w tle.
Java nie przestaje mnie zaskakiwać....
2
Pokaż kod tej swojej implementacji w C - myślę, że jest bardziej zaskakujący niż Java.
0
somekind napisał(a):
Pokaż kod tej swojej implementacji w C - myślę, że jest bardziej zaskakujący niż Java.
Kompilowane pod VS C++ 2015 do kodu 64-bitowego.
Każdy obieg pętli odpowiada pomnożeniu "akumulatora" przez 2^60 obliczone z użyciem przesuwania
Pod koniec obliczeń gdy nie da się już pojechać z użyciem 2^60 trzeba namnażać przez proste 2.
Żeby nie ganiać po całym buforze program na bieżąco ustala aktualny rozmiar akumulowanego wyniku.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIMIT 25000000
unsigned long long a[LIMIT];
unsigned long size=0; // Actual size (digits) of result
unsigned long newSize=0; //
inline void iteracja(void)
{
unsigned long i;
unsigned char carry=0;
for(i=0;i<size+2;i++)
{
a[i] <<= 1;
a[i]+=carry;
if(a[i]>=10)
{
a[i]-=10;
carry=1;
}
else
{
carry = 0;
}
if(a[i])
{
newSize=i;
}
}
size = newSize;
}
inline void iteracja4(void)
{
unsigned long i;
unsigned long stop;
unsigned long long carry=0;
unsigned long long pom=0;
stop = size+20;
for(i=0;i<stop;i++)
{
pom=a[i]<<60;
pom+=carry;
carry=pom/10;
a[i]=pom-10*carry;
if(a[i])
{
newSize=i;
}
}
size = newSize;
}
int show(void)
{
signed long i;
char inside=0;
int index = 0;
puts("The result is:");
puts("");
for(i=LIMIT-1;i>=0;i--)
{
if(a[i]!=0)
{
inside=1;
}
if(inside)
{
printf("%I64d",a[i]);
index++;
}
if(index==80)
{
printf("\r\n");
index = 0;
}
}
puts("");
puts("");
return 0;
}
void store_result(unsigned long power)
{
char name[256] = {0};
FILE* output;
int write = 0;
int index = 0;
signed int i = (25*1024*1024)-1;
sprintf(name,"%d.txt",power);
output = fopen(name,"wt");
for(;i >= 0;i--)
{
if(a[i])
{
write = 1;
}
if(write)
{
fprintf(output,"%c",0x30+(int)a[i]);
index++;
if(index==80)
{
fprintf(output,"\n");
index = 0;
}
}
}
fflush(output);
fclose(output);
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long i;
unsigned long j;
clock_t time_start;
clock_t time_actual;
int index = 0;
a[0] = 1;
time_start = clock();
i = 82589933;
i = 1000000;
// i = 64;
// i = 128;
// i = 16;
j = i;
printf("Calculating 2 rised to %d power\r\n",i);
puts("");
do
{
if(i>=60)
{
iteracja4();
i -= 60;
}
else
{
iteracja();
i--;
}
index++;
if((index%10000)==0)
{
time_actual = clock();
printf("%ld %ld %ld %lf\r\n",index,60*index,size,(double)(time_actual - time_start)/CLOCKS_PER_SEC);
// store_result(60*index);
}
}
while(i!=0);
time_actual = clock();
printf("%ld %ld %lf\r\n",j,size,(double)(time_actual-time_start)/CLOCKS_PER_SEC);
show();
// store_result(j);
return 0;
}
0
somekind napisał(a):
Pokaż kod tej swojej implementacji w C - myślę, że jest bardziej zaskakujący niż Java.
Dla porządku kod w Javie który robi to samo wygląda tak.
Pozostaje tylko do ustalenia na co program potrzebuje te trzy minuty.
Na wykonanie "shiftu" czy na zamianie BigInteger na string....
import java.math.BigInteger;
public class DwaDoN
{
public static void main(String[] args)
{
BigInteger alfa = new BigInteger("1");
String txt = new String("");
BigInteger result;
result = alfa.shiftLeft(82589933);
// result = alfa.shiftLeft(1000000);
txt = result.toString();
int index=0;
for(int i=0;i<txt.length();i++)
{
System.out.print(txt.charAt(i));
index++;
if(index==200)
{
index=0;
System.out.println();
}
}
System.out.println();
}
}
0
Nie chcę być złym piewcą ale w pierwszym poście napisałeś 2^282589933 − 1 a w kolejnym piszesz o 82585933. Kod w javie też korzysta z 82589933 a to jest ~nieznacznie mniej niż 282589933. Dodatkowo w kodzie z C mógłbyś zrobić szybkie mnożenie + mnożenie macierzowe coś ala http://mathworld.wolfram.com/FibonacciQ-Matrix.html - według mnie przyśpieszyło by to cały algorytm znacznie.
//Edit: sprawdziłeś czy wynik algorytmu z C / Javy są takie same oraz czy są one równe tej liczbie? Najpierw zweryfikowałbym czy algorytm liczy to co ma liczyć ;)
0
Chyba Mylisz szybkie mnożenie z szybkim liczeniem wyrazów ciągu Fibonacciego.
0
lubie_programowac napisał(a):
Nie chcę być złym piewcą ale w pierwszym poście napisałeś 2^282589933 − 1 a w kolejnym piszesz o 82585933. Kod w javie też korzysta z 82589933 a to jest ~nieznacznie mniej niż 282589933. Dodatkowo w kodzie z C mógłbyś zrobić szybkie mnożenie + mnożenie macierzowe coś ala http://mathworld.wolfram.com/FibonacciQ-Matrix.html - według mnie przyśpieszyło by to cały algorytm znacznie.
//Edit: sprawdziłeś czy wynik algorytmu z C / Javy są takie same oraz czy są one równe tej liczbie? Najpierw zweryfikowałbym czy algorytm liczy to co ma liczyć ;)
- Błąd jest oczywisty ma być 2^82 milionów - największa znana liczba pierwsza wg. info z Wikipedii.
- Wyniki mojego algo + kodu w Javie są OK, porównane z plikiem wzorcem pobranym z netu.
0
MrWebsky napisał(a):
somekind napisał(a):
Pokaż kod tej swojej implementacji w C - myślę, że jest bardziej zaskakujący niż Java.
Tak jak się spodziewałem. Samo wywołanie shiftowania to milisekundy.
Schody zaczynają się po wywołaniu konwersji do String, to ona trwa.
Kompilator online nie radzi sobie z perspektywą walki z liczbą o 25 milionach cyfr.
0
@MarekR
W Javie masz rację, gdyby darować sobie formatowanie (200znaków w linii) można to zrobić jedną instrukcją. W C ten numer nie przejdzie, zawartość tablicy musiałaby zostać skonwertowana do ASCII i przesunięta tak aby otrzymany łańcuch startował na indeksie zero. I to wszystko dopiero po przyjęciu założenia, że tablica robocza ma dane typu unsigned char. Próbowałem i taki wariant, ale konwersje unsigned char -> unsigned long long zżerają cały zysk z mniejszego potoku danych do/z RAM. Na procach Intela zysk z użycia unsigned char okazał się symboliczny.
0
THX wszystkim za uwagę.
Z mojej strony EOT.