Liczby pierwsze - kod na arduino

[ElektronicznySt]

Witam,
Czy dałoby się jakoś przerobić poniższy kod na Arduino tak, aby wyświetlane były liczby pierwsze z danego przedziału?? Próbuję go przetransponować, ale mi to nie wychodzi (

 List<uint> pierwsze = new List<uint>();
           for (uint i = 100000000; i < uint.MaxValue; i++)
           {
               bool pierwsza = true;
               for (uint n = 2; n < i; n++)
               {
                   if (i % n == 0)
                   {
                       pierwsza = false;
                       break;
                   }
               }
               if (pierwsza)
               {
                   pierwsze.Add(i);
               }
           }
           foreach (uint p in pierwsze)
           {
               Console.WriteLine( p.ToString());
           }

[marek1707]

A jak sobie naszą pomoc wyobrażasz? Że ktoś napisze kod? Czy odpowie: "tak, da się".

Pokaż co już zrobiłeś, jakie są wyniki tego nowego programu i co to znaczy "nie wychodzi"? Albo inaczej: opowiedz nam jak ten (powyższy) program działa - już samo to może bardzo Ci pomóc. Mówienie do żółtej kaczuszki naprawdę działa, spróbuj.

[sosnus]

Po pierwsze, jesteś w stanie słowami opowiedzieć jak działa algorytm wyszukiwania liczb pierwszych? Podpowiem, że taki algorytm ma nawet swoją nazwę, zaczynającą się na literę "S"

Drugie pytanie, czy znasz podstawy programowania pod Arduino?

Jeżeli odpowiesz sobie na te dwa pytania, a będziesz miał problem jak zaimplementować algorytm "S..." na platformie Arduino, to daj znać, gdzie konkretnie leży problem.

[ElektronicznySt]

AD- 1: Sito Eratostenesa

AD- 2: Tak

Ech, jak zwykle docinki i pretensjonalne teksty- - ludzie święta są, Pan Jezus Was kocha, więc nie musicie udawać takich ważniaków przed całym światem!

Dam sobie radę bez Waszej pomocy, tylko potrwa to trochę dłużej i tyle!

[marek1707]

"Dam sobie radę bez Waszej pomocy"

Moim zdaniem ten wniosek to najlepsza pomoc jaką mogłeś tu uzyskać. Czasem muszę napisać kilo tekstu, żeby ktoś do tego doszedł. Brawo za wiarę w siebie i determinację. Oby więcej takich ludzi.

[Elvis]

Ja tylko podpowiem, że algorytm który przysłałeś to NIE jest sito Erastotenesa.

[ElektronicznySt]

Szanowni,
a czy ten kod w Javie jest dobrym sitem??

public class Main 
{
   public static void main(String[] args)
   {
       int n = 100;
       boolean[] numbersTable = new boolean[n+1];
       for(int i = 2; i*i <= n; i++)
       {
           if (numbersTable[i] == true)
	continue;
           for (int j = 2 * i ; j <= n; j += i)
	numbersTable[j] = true;


       }
       System.out.println("Liczby pierwsze z przedziału od 2 do " + n + ":");
       for (int i = 2; i <= n; i++)
           if (numbersTable[i] == false)
	System.out.println(i);


   }


}

[Elvis]

Teraz juz duzo lepiej - to jest algorytm nazywany Sitem Erastotenesa. Tak z ciekawosci zapytam, co probujesz zrobic? Bo jesli tylko pobawic sie w implementacje klasycznych algorytmow to ok, ale jesli chcesz zrobic cokolwiek wiecej to Arduino jest chyba najgorszym wyborem. Wolny procesor i bardzo malo RAM-u, wiec raczej za duzych liczb pierwszych tak nie znajdziesz.

[ElektronicznySt]

Już tłumaczę: chciałbym porównać prędkość/ wydajność poszczególnych płytek Arduino na podstawie szybkości znajdywania liczb pierwszych.

[Elvis]

Pomysl fajny, tylko pamietaj, ze masz bardzo malo pamieci RAM - np. atmega328 ma raptem 2KB pamieci, wiec jesli rozrzutnie zadeklarujesz tablice jako bool, maksymalnie najedziesz liczby pierwsze mniejsze od 2000, wiec pewnie czas dzialania programu bedzie trudny do zmierzenia.

Mozesz pocwiczyc programowanie i uzywac pojedynczych bitow do przychowywania informacji o tym czy liczba jest pierwsza, czy zlozona. Wtedy mozesz szukac liczb z zakresu do blisko 16000 - jednak to nadal bedzie dzialac bardzo szybko, nie dajac sensownego porownania predkosci.

Jesli koniecznie chcesz testowac predkosc Arduino, lepiej poszukaj przykladu, ktory wymaga duzo obliczen, a mniej pamieci RAM.

[ElektronicznySt]

o faktycznie, o tym nie pomyślałem to ten pomysł wypałiłby jedynie z Arduino Due, bo płytki bardziej budżetowe zbyt szybko się zatkają...

[marek1707]

Ale przecież nie trzeba daleko szukać by zamulić biedne Arduino. Prosto napisana faktoryzacja dużych liczb (czyli szukanie podzielników) wymaga niewiele pamięci a załatwia AVR na długo. Już test na uint32_t wykonuje się na oko kilka sekund (podzielniki 2..65536) a jeśli odpalisz uint64_t to musisz ograniczyć zakres, bo wcześniej płytka zgnije od wilgoci w powietrzu. Poniższy kod liczy się na 8MHz MiniPro ok minuty, nie liczyłem dokładnie:

  uint64_t
   x = 230948548071,
   d;

 for (d = 2; d<480571; d++)
 {
   uint32_t w = x/d;
   if (x == (w*d))
   {
     uint32_t tmp;
       tmp = uint32_t(d>>32);
       Serial.print(tmp,HEX);
       tmp = uint32_t(d);
       Serial.println(tmp,HEX);
   }
 }
 Serial.println("*");

Oczywiście podzielniki sprawdzamy tylko do wielkości pierwiastka kwadratowego z liczby wejściowej. W przykładzie koniec pętli policzyłem ręcznie na kalkulatorze, a samą liczbę wpisałem z sufitu, ma "tylko" 38 bitów więc szanse na rozwój są ogromne

[Elvis]

Wydaje mi się, że wstawianie print-ów do benchmarka, to nie najlepszy pomysł - nie dają informacji o wydajności płytki, ale raczej o jakości implementacji biblioteki oraz prędkości transmisji. Jeśli print-y chodzą po porcie szeregowym, to spowolnią całą zabawę i sam pomiar będzie mocno zaburzony.

Chyba lepiej byłoby np. na koniec wypisać liczbę podzielników, zamiast wypisywać wszystkie.

[marek1707]

Te printy są buforowane a z resztą podzielników nie ma dużo - to tylko przykład programu. Zawsze można wybrać jakąś dużą liczbę pierwszą i wypisać tylko końcową gwiazdkę

Ponieważ nie wiemy jakie własności procesora benchmark ma testować (i po co to w ogóle, skoro w Arduino mamy albo przewidywalne AVRy albo czasem ARMy), to wszystko jest wróżeniem z fusów.