Za duża liczba...

[kuicets]

Czy jestnieje język, który wczyta mi poprawnie liczbę 2^127 ???

 

Jest to dla mnie ważne, gdyz zajmuję sie liczbami pierwszymi i będzie to duży krok na przód jeżeli 2^127 - 1 będzie liczbą pierwszą. Nie jestem programistą i dotychczas miałem tylko styczność z turbo pascalem. Tam moge dobic do 2^30. Troche za mało :D...

 

Z samym algorytmem i wszystkim dam sobie rade. Chodzi tylko o to czy jest mozliwe wczytanie takiej liczby gdzies. jestem rownież świadom, iż sprawdzanie może trwać...dłuuuuugo. Mysle jednak że z moim prockiem nie przebije tygodnia...:D

[spicum]

to jest kwestia odpowiedniej biblioteki :)

 

do C jest take cudo jak biblioteka CCMATH i obiekt bigInt (jakies ograniczenia mial ale nie pamietam jakie)

 

w javie jest java.math.BigInteger (z tego co pamietam wielkosc jest ograniczona tylko pamiecia maszyny)

 

pewnie jest tego duzo wiecej ale te jestem w stanie przypomniec sobie od razu :>

 

na pewno zrobili cos do High Performance Fortran (uzywny do obliczen wielkiej skali)

pewno dla C znajdzie sie cos jeszcze w bibliotekach numerycznych typu 'nr' czy 'numlib'

[Megabyte]

To kwestia raczej umiejetności. Zawsze można samemu oprogramować przechowywanie takich liczb i operacje na nich

[Met]

Polecam biblioteke bignum co C++ - polska i dobra ;))

 

http://panoramix.ift.uni.wroc.pl/~bosy/bignum.htm

 

od razu masz tam link do przykladowego programu udowadnajacego ze 2^512+1 nie jest liczba pierwsza ;)

[kuicets]

Slicznie dziekuje, jak coś to sie jeszcze zglosze...

[kuicets]

Met, a czy mógłbyś mi to przerobić na program sprawdzający 2^127 - 1 i zapisac to w konwencji programu a nie w notatniku?

 

Byłbym wdzięczny, znam sie jedynie (i to w bardzo małym stopniu) na pascalu...

[Polar]

Nie jestem programistą i dotychczas miałem tylko styczność z turbo pascalem. Tam moge dobic do 2^30. Troche za mało :D...

A dlaczego tylko do 2^30 ??? . Czy chodzi ci o moc procesora czy o typ liczbowy ?.

 

Jakby co to w c++ w bibliotece stdint.h jest coś takiego jak int64 (–2^63..2^63–1) a także uint64 (0..2^64-1)

Dodajesz na początku #include <stdint> , a potem w programie delkarujesz sobie int64_t nazwa_zmiennej ;

 

Nie wiem jaki masz algorytm ale obliczenie czy 2^63 jest czy nie jest pierwszą trochę by trwało :) .

[kuicets]

Jezeli chodzi o turbo padcala, to przy deklarowaniu zmiennych najwiekszy jest longint i tak na przyklad:

var a: longint;

 

powoduje, ze a moze być od -(2^32) do 2^32 (chyba)

o to mi chodzilo. Procesor raczej nie jest ograniczeniem

[Polar]

var a: longint;

powoduje, ze a moze być od -(2^32) do 2^32 (chyba)

No faktycznie zapomniałem że Pascal jest jeszcze na 16 bitach , kompilator :D. Ehh te stare czasy :roll:

[ULLISSES]

sprawdzilem kalkulatorem i sprawa wyglada tak:

 

sprawdzenie, czy (2^127)-1 jest liczba pierwsza na kompie 1,8GHz zajelo by Ci ponad 265 dni, zakladajac iz na sprawdzenie 1 liczby procesor uzywa 10 polecen (i sprawdza tylko nieparzyste) i nie robi w tym czasie NIC INNEGO (DOSLOWNIE!) - oczywiscie takie warunki sa niemozliwe, a 10 polecen jest mozliwe tylko przy napisaniu programu w assemblerze... chociaz tego ostatniego nie jestem pewien, bo nie znam sie za bardzo na ASM - powiedzmy, ze zgaduje

 

reasumujac: na normlanym kompie nie dowiesz sie, czy ta liczba to liczba pierwsza...

nawet sprawdzenie liczby 2^31 to kawal czasu...

 

chyba ze np podzielisz te liczbe na okolo 1000 przedialow i dasz ludziom w sieci do sprawdzenia po 1 z przedialow - wtedy dowiesz sie moze po 1 dniu (przy wykorzystaniu wstawek ASM i priorytecie REAL TIME dla progamu)

 

oczywiscie caly ostatni akapit to czysta teoria oparta na fakcie, iz procesor nie moze sprawdzac 1 liczby 1 poleceniem i ze musi tez obslugiwac inne programy podczas obliczen - REAL TIME ma zapewnic jak najmniejsze odwracanie uwagi procesora od obliczen

 

chyba ze by na konsole program pisac (pod czysty dos) - podobno to system 1-no zadaniowy, wiec teoretycznie powinien nie robic nic innego podczas obliczen...

[Gość]

A po co chcesz sprawdzac tak małe liczby, skoro obecnie znane sa juz duzo (duzo duzo) wieksze liczby pierwsze.

Polecam odwiedzic strone http://www.mersenne.org/prime.htm

Tak.. to Ci sami od Prime95...

 

sprawdzenie, czy (2^127)-1 jest liczba pierwsza na kompie 1,8GHz zajelo by Ci ponad 265 dni

Chyba metodą brute-force...

 

BTW na stronie podanej wyzej sa tez dostepne zrodla.. wiec nic nie zaszkodzi zobaczyc jak ludzie zajmujacy sie tym sprawdzaja te liczby.

[ULLISSES]

Chyba metodą brute-force...

Hehe

No tak... :D

 

W sumie po 12 godzinach zajec na uczelni nie mysle logicznie - nie wpadlem na to, aby np uzyc jakiegos algorytmu - chyba o takim slyszalem kiedys na "algorytmach i strukturach danych"...

 

dopisek:

 

rzucilem okiem na stronke tamta - liczba (2^24036583)-1 - jak sie do tego ma 2^127?

1. Ci ludzie sie Nudza przez bardzo duze "N"...

2. po co im takie duze liczby pierwsze? do czego to sie moze przydac? dla samej swiadomosci ze taka istnieje? jesli tak, to wraz z rozwijem elektroniki tak bedzie sie mozna bawic w nieskonczonosc...

 

ps. ponad 7 milionow cyfr? czyli ponad 7MB w pamieci ... jeszcze raz: po co oni to robia?

[Domik]

potrzebują je do szyfrowania ale jak to robią to dokładnie nie wiem ;) ładna cyferka 7 mb

[Polar]

nawet sprawdzenie liczby 2^31 to kawal czasu...

Jakiś ułamek sekundy 2^31 == 2147483648 ... od razu widać że dzieli się przez 2 czyli na pewno nie jest LP :)

 

W sumie tu nie chodzi nawet o sprzęt tylko o dobrze napisany algorytm który już przy tych powiedzmy najmniejszych dzielnikach 2,3,5,7,11,13,17 to powie :x

[ULLISSES]

Jakiś ułamek sekundy 2^31 == 2147483648 ... od razu widać że dzieli się przez 2 czyli

hehe, moj blad..

to z rozpedu - chodzilo mi o 2^31-1..

 

o dobrze napisany algorytm który już przy tych powiedzmy najmniejszych dzielnikach 2,3,5,7,11,13,17 to powie

hmm.... kolejne trafne spostrzezenie...

nie mniej jednak przy 7 ml cyfr to te 'najmniejsze dzielniki' to calkiem dlugie lancuszki, bo inaczej nie trwalo by to 2 tygodnie na P2,4GHz czy jakos tak...

 

a ze do szyfrowania to sie stosuje, to zapomnialem - czytalem kiedys cos o tym (ale starosc nie radosc)

swoja droga kwestia zlamania dowolnego szyfru to nie kwestia mozliwosci (da sie/ nie da sie) lecz czasu

przeciez zwykle kompy nie sa w stanie zlamac obecnie najlepszych szyfrow w czasie nawet w miare dalekim od przyzwoitego...

 

swoja droga, jak oni szukaja tych liczb? musza miec calkiem ciekawe biblioteki obslugujace te kosmiczne liczby...

chyba, ze traktuja te liczby jako tablice liczb (lub cyfr)... wtedy mozna miec taka liczbe, jaka jest w stanie pomiescic pamiec... tyle ze operacje na tym, to juz inna bajka...

 

ps. sorki za totalny off-topic...

[Gość]

Co do tego czemu to dziala tak szybko to tu: http://www.mersenne.org/math.htm jest wiekszosc czesci matematycznej opisana, wiec mozna poczytac :)

Jest podany algorytm szybkiego sprawdzania czy dana liczba dzieli liczbe 2^P-1 i wiele innych ciekawostek.

 

Pozatym najwieksza liczbą, która trzeba sprawdzic czy jest dzielnikiem 2^P-1 jest jej pierwiastek, a wiec w ogolnym zapisie liczba bliska 2^(P/2) - 1, czyli dla wykladnika wynoszacego troche ponad 24mln wystarczy sprawdzic "jedynie" liczby do ok 2^(12mln), co sporo upraszcza sprawe.

[marcinEc]

Jest to dla mnie ważne, gdyz zajmuję sie liczbami pierwszymi i będzie to duży krok na przód jeżeli 2^127 - 1 będzie liczbą pierwszą. Nie jestem programistą i dotychczas miałem tylko styczność z turbo pascalem. Tam moge dobic do 2^30. Troche za mało :D...

"A Mersenne prime is a prime of the form 2^P-1. The first Mersenne primes are 3, 7, 31, 127, etc. There are only 41 known Mersenne primes."

 

I po co ta cała dyskusja? 2^127-1 jest liczbą pierwszą Mersenna M127.

 

A co do sprawdzania liczb pierwszych to żyjemy w XXI wieku i trochę już o nich wiemy... Może warto poszukać tej wiedzy, a nie rzucać własne chybione teorie? :?

[kuicets]

I o to mi chodzilo. Dzieki...