Największa liczba pierwsza.

0

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
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ć ;)

  1. Błąd jest oczywisty ma być 2^82 milionów - największa znana liczba pierwsza wg. info z Wikipedii.
  2. Wyniki mojego algo + kodu w Javie są OK, porównane z plikiem wzorcem pobranym z netu.

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