ANSI C: Test di numeri primi con la Wheel Factorization

Crivello di eratostene: animazioneCosa sono i numeri primi e perché tanto interesse intorno a loro? Un numero n > 0 si definisce primo se è divisibile solo per 1 e per sé stesso con resto 0. L’interesse è dovuto a due motivi, principalmente:

1) I numeri primi sono le basi di tutta l’aritmetica come si può evincere dal Teorema Fondamentale della matematica che recita:“Ogni intero si fattorizza in modo unico come prodotto di numeri primi” e questo li rende indubbiamente affascinanti.
2) I numeri primi molto grandi (ordine di 21024), sono alla base del più utilizzato sistema di crittografia: l’RSA questo invece, attira molto gli esperti in sicurezza informatica…!

Come si trovano i numeri primi?

Fu Eratostene di Cirene (276 – 194 a.c.), il primo a proporre un metodo per “setacciare” i numeri primi, detto appunto: crivello di Eratostene. Esistono diversi algoritmi che risolvono il crivello di Eratostene, questo che propongo mi sembra il più efficiente. Supponiamo dunque di voler trovare tutti i numeri primi da 1 a n, l’algoritmo in pseudocodice è il seguente:


for i := 2 to n-1 do
 a[i] := 1
for i := 2 to n-1 do
 if a[i]
  for j := i to (j*i)<n do
   a[i*j] := 0
for i := 2 to n-1 do
 if a[i]
  print i

In pratica si procede da i=2 a n, eliminando tutti i multipli di i
(nella immagine in alto a sinistra è possibile vedere un’animazione del processo). Va detto che ancora oggi, pur non essendo l’algoritmo più efficiente in assoluto, è molto utilizzato quando si lavora su numeri relativamente piccoli, per la sua estrema semplicità.

Il metodo della ruota di fattorizzazione (Wheel Factorization)

Già il crivello di Eratostene permette un notevole incremento di prestazioni rispetto ad un processo di “forza bruta” specialmente se l’algoritmo è opportunamente ottimizzato. Il metodo della ruota risulta ancora più efficiente, e vediamo il perché:
Si scelgono inizialmente come numeri primi di partenza: 2, 3, 5 per ottenere una ruota di lunghezza 30. La lunghezza della ruota è determinta dal prodotto dei numeri primi che decidiamo di utilizzare. Nel nostro caso 2 * 3 * 5 = 30. A questo punto troviamo tutti gli interi che non sono multipli di 2, 3 e 5, il vettore risultate sarà: s[] = {1, 7, 11, 13, 17, 19, 23, 29 }. Abbiamo ottenuto un insieme di numeri che, non sono multipli di 2, 3, 5 e anche se sommati alla lunghezza della ruota o ai suoi multipli (30, 60, 90, ecc), non daranno mai multipli di 2, 3, 5.
Il concetto è più chiaro osservando la figura sotto, le colonne gialle della tabella contengono i soli numeri che andremo a testare, i rimanenenti non sono sicuramente primi, esclusi i numeri di partenza (2, 3, 5). Se provassimo a visualizzare ciascuna riga della tabella come una circonferenza, potremmo immaginare la tabella come una ruota in cui le colonne gialle rappresentano i raggi dove cercare i numeri primi.

Tabella di fattorizzazione
Tabella di fattorizzazione

Il codice è tratto dall’articolo: “Prime Number Determination Using Wheel Factorization” di rickoshay originariamente scritto in C#, e da me convertito in ANSI C


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio .h>
#include <stdlib .h>
 
unsigned long FirstDivisor(unsigned long candidatePrime);
int isPrime(unsigned long primeSuspect);
 
unsigned long FirstDivisor(unsigned long candidatePrime)
{
 const int wheelFactor = 30;
 int aSieve30[] = {7, 11, 13, 17, 19, 23, 29, 31};
 int firstPrimes[] = {2, 3, 5}, i;
 unsigned long sqrtmax, pass;
 
 if (candidatePrime == 1)
 {  
    return 0;
 }
 for (i=0;i<sizeof (firstPrimes)/sizeof(int);i++) {
     if (candidatePrime % firstPrimes[i] == 0) {
        return firstPrimes[i];
     }
 }
 
 sqrtmax  = (unsigned long) sqrt(candidatePrime);
 for (pass=0; pass<sqrtmax; pass+=wheelFactor) {
  for (i=0;i<sizeof(aSieve30)/sizeof(int);i++) {
      if (candidatePrime % (pass + aSieve30[i]) == 0) {
         return pass + aSieve30[i];
      }
  }   
 }
 return candidatePrime; 
}
 
int isPrime(unsigned long primeSuspect)
{
   if (primeSuspect == 0) {
      return 0;
   }
   if (FirstDivisor(primeSuspect) == primeSuspect) {
      return 1;
   }
   else {
      return 0;
   }
}
 
int main(int argc, char *argv[])
{
  unsigned long x, i;
 
  if (argc == 2) {
     x = strtoul(argv[1],NULL,10);
     if (isPrime(x)) {
        printf("%u e' un numero primo\n",x);
     }
     else {
        printf("%u non e' un numero primo\n",x);        
     }     
  }
  else {
   printf ("\nUsage: %s n \nWhere n is an integer number to check for primality\n",argv[0]);
  }
  system("PAUSE");	
  return 0;
}

Download

Il download dell’applicazione (compilata per Win32) è disponibile qui, in formato compresso zip. Sono compresi i sorgenti e i files di progetto per il compilatore DevC++ (ver.: 4.9.9.2). Per l’utilizzo è sufficiente lanciare il programma da una console DOS e passare come parametro il numero da testare.

Conclusioni:

Adottare il metodo della Wheel Factorization per testare la primalità di un numero, consente un incremento di performance pari a (1 – 8 /30) * 100 = 73% con una ruota di dimensioni 30. Le prestazioni possono crescere aumentando le dimensioni della ruota, specialmente quando si ragiona con numeri abbastanza grandi. Il codice proposto utilizza al massimo numeri di 4 byte (unsigned long int = 4,294,967,295) e le performance rimangono accettabili ricompilando per numeri di 8 byte (unsigned long long = 18,446,744,073,709,551,615). In questo caso però sarebbe consigliabile utilizzare una ruota prodotta dai primi 8 numeri primi, come suggerito nell’articolo da cui ho tratto lo spunto per il codice.

Riferimenti ed approfondimenti:

C/C++ come condividere dati fra diversi processi con una DLL

compilatori C/C++

Le DLL sono librerie di funzioni, che necessitano di altri programmi per essere eseguite. Chiunque è in grado di costruirsi la propria libreria di funzioni, semplicemente con la conoscenza del linguaggio C o C++ e un compilatore. Fra questi ce ne sono in particolare due molto usati e gratuiti: Bloodshed DevC++ con licenza GNU e Microsoft Visual C++ Express che pure è un ambiente di sviluppo gratuito con limitazioni più che altro nei wizard e negli strumenti di aiuto.

Normalmente, se costruiamo una DLL e questa viene utilizzata da diverse applicazioni ogni processo che carica quella DLL avrà la sua copia delle variabili, anche fossero dichiarate come globali. Questo è un comportamento del tutto logico e consente di dare stabilità e sicurezza al sistema.
Potrebbe tuttavia esserci la necessità di condividere dati fra processi diversi, in questo caso esiste un modo di dichiarare una variabile in una sezione di memoria condivisa.
Vediamo come condividere una variabile che chiameremo banalmente sharedint, appunto di tipo int, utilizzando la sintassi adatta in modo specifico al compilatore Visual C++, vedremo in seguito come ottenere lo stesso risultato utilizzando il compilatore Bloodshed DevC++ (che si appoggia a gcc).
Per prima cosa, dobbiamo fornire al pre-processore le seguenti direttive pragma:

1
2
3
4
5
#pragma data_seg("SHARED")  // Begin the shared data segment.
// Define variable
int sharedint = 0;
#pragma data_seg()          // End the shared data segment 
#pragma comment(linker, "/section:SHARED,RWS")

Quindi definiamo la funzione DllMain che deve essere sempre presente in qualsiasi DLL. In realtà, quando scegliamo un progetto di tipo DLL sarà l’IDE stesso a scrivere questo per noi!
Notate che la funzione è preceduta da due modificatori: il primo: BOOL non è altro che un typedef ad un int ed è definito nell’header windows.h il secondo: APIENTRY, più interessante, è un typedef a WINAPI che è a sua volta un typedef a _stdcall. Si tratta di una calling convention che impone alla funzione chiamata di ripulire lo stack, compito che di default ( _cdecl ) viene invece eseguito dal chiamante. Se utilizzeremo la nostra DLL in Visual Basic, è richiesto l’utilizzo di _stdcall.
Infine definiamo due funzioni, che saranno quelle esportate dalla DLL:

  • SetNumber(int num1) che prende come input un intero e lo memorizza nella variabile definita nell’area di memoria condivisa
  • GetNumber() che restituisce l’intero impostato nella variabile definita nell’area di memoria condivisa

Ecco il codice completo per Visual C++:

// dllmain.cpp: definisce il punto di ingresso per l'applicazione DLL.
#include "stdafx.h"
 
#pragma data_seg("SHARED")  // Begin the shared data segment.
// Define variable
int sharedint = 0;
#pragma data_seg()          // End the shared data segment 
#pragma comment(linker, "/section:SHARED,RWS")
 
 
BOOL APIENTRY DllMain( HMODULE hModule,
                       DWORD  ul_reason_for_call,
                       LPVOID lpReserved
					 )
{
	switch (ul_reason_for_call)
	{
	case DLL_PROCESS_ATTACH:
	case DLL_THREAD_ATTACH:
	case DLL_THREAD_DETACH:
	case DLL_PROCESS_DETACH:
		break;
	}
	return TRUE;
}
 
 
int __stdcall SetNumber(int num1)
{
	sharedint = num1;
	return TRUE;
}
int __stdcall GetNumber ()
{
	return sharedint;
}

Ci siamo quasi, ma prima di compilare dovremo informare il linker quali sono le funzioni che vogliamo esportare. Questo avviene preparando un file di definizioni (.def) in questo modo:

LIBRARY shareIntVc.dll
EXPORTS
SetNumber
GetNumber

Impostiamo il riferimento al file DEF nella finestra delle proprietà del progetto come nella figura qui sotto:

proprieta' del linker

Compiliamo ed il gioco è fatto! Se non abbiamo avuto errori dal compilatore, troveremo la DLL nella sottocartella del progetto: debug.

Il progetto per Visual C++ 2008 lo potete prelevare qui.
Per testare la DLL potete prelevare questo progetto in Visual Basic 6, avendo cura di modificare il file module1.bas (che contiene le dichiarazioni delle funzioni importate), indicando il percorso corretto della DLL sul vostro PC e ricompilando il sorgente. Lanciando più istanze dell’eseguibile Visual Basic sarà possibile leggere da ogni istanza la variabile impostata.

Vediamo infine come cambia il codice della nostra DLL utilizzando il compilatore Bloodshed DevC++: l’unica differenza sta nella sostituzione delle direttive pragma con: l’utilizzo dello specificatore di attributi delle variabili : __attribute__((section ("shared"), shared))
Ecco il codice completo per Bloodshed DevC++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <windows.h>
#include <stdio.h>
 
#include <stdlib.h>
 
int sharedint __attribute__((section ("shared"), shared)) = 0;
 
BOOL APIENTRY DllMain (HINSTANCE hInst     /* Library instance handle. */ ,
                       DWORD reason        /* Reason this function is being called. */ ,
                       LPVOID reserved     /* Not used. */ )
{
    switch (reason)
    {
      case DLL_PROCESS_ATTACH:
        break;
 
      case DLL_PROCESS_DETACH:
        break;
 
      case DLL_THREAD_ATTACH:
        break;
 
      case DLL_THREAD_DETACH:
        break;
    }
 
    /* Returns TRUE on success, FALSE on failure */
    return TRUE;
}
 
int _stdcall SetNumber(int num1) {
    sharedint = num1;
    return TRUE;
}
 
int _stdcall GetNumber() {
    return sharedint;
}

Anche qui è necessario definire le funzioni esportate in un file di definizioni che sarà identico a quello utilizzato con Visual C++, e impostarlo nella sezione “Opzioni del progetto” -> “Parametri” -> “Linker”, come mostrato nella figura qui sotto:

proprieta' del linker

Il progetto per Bloodshed DevC++ lo potete prelevare qui.

Conclusioni:

L’utilizzo della memoria condivisa con le DLL si rivela utile per scambiare dati fra diverse applicazioni, ma bisogna fare attenzione alle potenziali violazioni della memoria. Per ottenere un funzionamento sicuro, sarebbe necessario implementare un sistema di sicronizzazione dell’accesso ai dati condivisi attraverso un mutex o una critical section.

Riferimenti ed approfondimenti:


luciano ha scritto:

si ok l’ho provata e funziona perfettamente ..
mi chiedo se anziche un int volessi una una variabile stringa
come diventerebbela dll ?
ciao Luciano
02.11.10 18:50
Mario Spada ha scritto:

@Luciano: Con le stringhe il discorso si complica un poco perché il C tratta le stringhe come byte array terminate da un NULL char, mentre VB usa BSTR che sono stringhe unicode. Ad ogni modo la cosa è fattibile, e nemmeno troppo complicata. Purtroppo in questo momento non ho tempo di preparare un esempio, ma ti posso suggerire questi due link molto esaurienti:
1) http://sandsprite.com/CodeStuff/Writing_A_C_Dll_for_VB.html
2) http://support.microsoft.com/kb/187912
08.11.10 19:20