Prime number calculation program (finally in English)
samuell
Posts: 554
in Propeller 2
Hi all,
I've made a few changes to this program lately, mainly some slight housekeeping. Of course the code was also edited by others, but still needs some explaining on some of those edits, so that is the purpose of this thread. Mind that the original code was written by me, so some of the comments are still in Portuguese. This is just a version rigged up for the Propeller 2, to be used with FlexGUI. It works but with some limitations:
- The baud rate had to be toned down to 115200, so you will need to run it with [cmd.exe /c start "Propeller Output" "%D/bin/loadp2" %P -b115200 "%B" -t -k] if you are using a RevB board, or [cmd.exe /c start "Propeller Output" "%D/bin/loadp2" %P -b115200 "%B" -t -k] if you are using a RevA board;
- No support for very large numbers, as the program will produce the wrong output, as if you introduced other values;
- Still limited to 160MHz operation.
However, the code is stable enough for you to try it.
Although you can see the program code above, the same is also attached. Download and have fun!
Kind regards, Samuel Lourenço
I've made a few changes to this program lately, mainly some slight housekeeping. Of course the code was also edited by others, but still needs some explaining on some of those edits, so that is the purpose of this thread. Mind that the original code was written by me, so some of the comments are still in Portuguese. This is just a version rigged up for the Propeller 2, to be used with FlexGUI. It works but with some limitations:
- The baud rate had to be toned down to 115200, so you will need to run it with [cmd.exe /c start "Propeller Output" "%D/bin/loadp2" %P -b115200 "%B" -t -k] if you are using a RevB board, or [cmd.exe /c start "Propeller Output" "%D/bin/loadp2" %P -b115200 "%B" -t -k] if you are using a RevA board;
- No support for very large numbers, as the program will produce the wrong output, as if you introduced other values;
- Still limited to 160MHz operation.
However, the code is stable enough for you to try it.
/*
* Programa de cálculo de números primos para a placa de desenvolvimento
* "Prop II"
*
* Este programa foi criado para verificar o desempenho da placa "Prop II",
* mas pode ser utilizado com outras placas de desenvolvimento baseadas no
* Propeller P8X32A. O programa calcula números primos dentro de uma dada
* gama, cujos valores são introduzidos pelo utilizador.
*
* Nota:
* Para o máximo desempenho, o programa deve ser compilado utilizando o modelo
* de memória "LMM Main RAM". Deverá seleccionar a opção "Math Lib" no
* separador "Linker".
*
* Autor: Samuel Lourenço
* Data: 17 de Novembro de 2019
*/
// Includes
//#include <math.h>
#include <propeller.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h> // Changed order of include files as a quick workaround - To be discarded in future versions
#ifdef __FLEXC__
typedef unsigned long ULONG;
typedef long LONG;
#else
typedef unsigned long long ULONG;
typedef long long LONG;
#endif
// Protótipos
void init(void);
_Bool isprime(ULONG);
void isprime_cog(void* param);
// Variáveis globais
#define STACKSIZE 56
static short lockid;
unsigned int stacks[7][STACKSIZE];
static volatile _Bool flags[7] = {0, 0, 0, 0, 0, 0, 0}, results[7];
static volatile ULONG numbers[7] = {0, 0, 0, 0, 0, 0, 0};
/* Tanto o array "flags" como o array "numbers" são indicadores de estado, e por
* isso devem ser inicializados a zero. O array "flags" indica a disponibilidade
* de cada 'cog' (zero para "inactivo" e um para "activo"), ao passo que o
* array "numbers" é indicativo das tarefas, uma vez que armazena os números
* processar (um valor a zero significa que o 'cog' correspondente está livre).
* Estes arrays são implicitamente limpos depois da sessão de cálculo. O array
* "results" não é indicador de estado, pelo que não precisa de ser
* inicializado a zero. */
#ifdef __FLEXC__
int isqrt(int x)
{
__asm {
qsqrt x, #0
getqx x
};
return x;
}
#else
// Patch for P2 added here - Thanks Dave Hein!
int __attribute__((noinline)) isqrt(int x)
{
__asm__("qsqrt r0, #0");
__asm__("getqx r0");
}
int64_t __attribute__((noinline)) __umoddi3(int64_t x, int64_t y)
{
__asm__("setq r1");
__asm__("qdiv r0, r2");
__asm__("getqy r0");
__asm__("mov r1, #0");
}
// End of patch
#endif
void main(void)
{
LONG count, min, max, in, out;
char input[256];
#ifdef __FLEXC__
clkset(0x010007f8, 160000000);
_setbaud(115200); // 230400 baud fails to display some results!
pausems(1000);
#endif
init();
while (1)
{
count = 0;
min = 0;
max = 0;
/* É importante limpar as variáveis anteriores antes de cada ciclo de
* cálculo. */
while (min <= 0)
{
printf("Insert minimum value: ");
gets(input); // Lê a string introduzida
min = atol (input); // Converte para 'long long integer'
if (min <= 0) // Se o valor introduzido for menor ou igual a zero, ou não for um número
printf("The minimum value should be greater than zero!\n");
}
while (max <= 0)
{
printf("Insert maximum value: ");
gets(input); // Lê a string introduzida
max = atol (input); // Converte para 'long long integer'
if (max <= 0) // Se o valor introduzido for menor ou igual a zero, ou não for um número
printf("The maximum value should be greater than zero!\n");
}
if (min > max) // Se o valor mínimo for maior do que o valor máximo
printf("The minimum value cannot be greater than the maximum value!\n");
else // Se o valor mínimo for menor ou igual ao valor máximo
{
printf("\nCalculating prime numbers...\n\n");
out = in = min;
/* A variável "in" guarda o valor a introduzir, enquanto que a
* variável "out" serve para fazer uma gestão dos números a
* verificar depois do cálculo. Estas variáveis vão sendo
* incrementadas por cada número que é introduzido ou verificado no
* array "numbers". Note que o valor em "out" não corresponde
* necessariamente ao valor que está a ser extraído do array. */
while (out <= max)
{
short i;
for (i = 0; i < 7; i++) // Este ciclo "varre" os valores dos arrays "flags", "numbers" e "results"
{
if (!flags[i] && numbers[i] != 0) // Se o 'cog' estiver marcado como estando "inactivo" e o número não for zero
{
if (results[i]) // Se o número for primo
{
count++; // Incrementa o valor da variável "count", que serve para a contagem dos números primos
printf("%d:\t%u\n", (int)count, (unsigned int)numbers[i]); // Imprime a contagem e o número
}
numbers[i] = 0; // Uma vez verificado se é primo ou não, limpa o número na posição 'i'
out++; // Incrementa o valor da variável "out"
}
if (in <= max && numbers[i] == 0) // Se houver novos números a introduzir e se houver 'cogs' livres
{
numbers[i] = (ULONG)in; // Introduz o número da variável "in" no array "numbers", posição 'i'
flags[i] = 1; // Marca o 'cog' correspondente ao índex como "activo", efectivamente dando sinal ao mesmo para arrancar
in++; // Incrementa o valor de "in"
}
}
}
#ifdef __FLEXC__
printf("\n%ld prime number(s) found.\n\n", count); // Apresenta a contagem final de números primos
#else
printf("\n%lld prime number(s) found.\n\n", count); // Apresenta a contagem final de números primos
#endif
}
}
}
void init (void) // Rotina de inicialização do micro-controlador
{
short i;
for (i = 0; i < 7; i++) // Os 'cogs' 1 a 7 são inicializados aqui, sempre com a mesma rotina
{
cogstart(isprime_cog, NULL, &stacks[i][0], STACKSIZE*sizeof(unsigned int)); // Inicia cada 'cog' com a rotina "isprime_cog" e atribui-lhe o seu 'stack'
// Important: No need to do "STACKSIZE*sizeof(unsigned int)" as "sizeof(stacks[i])" will return the correct size of an int32 array. Any rationale for that?
// "sizeof(stacks[i])" would return the incorrect value if "stacks[i]" was passed as a pointer, which is not the case here!
// And why the address of "stacks[i][0]"?
}
}
_Bool isprime(ULONG number) // Função para cálculo de números primos
{
/* Esta pode ser considerada a função central do programa. Para ver se um
* dado número é primo ou não, primeiro verifica-se se o mesmo é um, dois,
* três, ou se é divisível por dois ou três. Considera-se que se o número
* for igual a um, ou divisível por dois ou três, não é primo. Sendo dois
* ou três, é primo. Não se satisfazendo qualquer das condições
* anteriores, verifica-se se o número é divisível por todos os números
* ímpares não múltiplos de três, a partir de cinco até (pelo menos) ao
* inteiro da raiz quadrada do mesmo (inclusive). Repare que não é
* necessário ensaiar todas as divisões até o quociente ser igual ao
* próprio número. Deste modo, o algoritmo fica muito mais rápido. */
_Bool retval;
unsigned long sqrt_num;
if (number == 2 || number == 3) // Se o número for dois ou três
retval = 1; // então é primo
else if (number < 2 || number % 2 == 0 || number % 3 == 0) // Se for zero ou um, ou divisível por dois ou por três (não sendo dois ou três)
retval = 0; // não é primo
else
{
retval = 1; // Assume-se que o número é primo, até haver uma divisão inteira
sqrt_num = (unsigned long)isqrt(number); // Calcula previamente a raíz quadrada do número
unsigned long n;
for (n = 5; n <= sqrt_num; n += 6) // Ciclo onde são testadas as divisões por números ímpares que não sejam múltiplos de três
{
if (number % n == 0 || number % (n + 2) == 0) // Se a divisão por 'n' ou por 'n + 2' for inteira
{
retval = 0; // o número não é primo
break; // Sai do ciclo
}
}
}
return retval; // Retorna o valor um se o número dado for primo, e zero se não o for
}
void isprime_cog(void *param) // Rotina dedicada a cada 'cog'
{
_Bool flag, result;
unsigned long mask;
ULONG number;
short i = cogid() - 1; // Vê de antemão qual é o 'cog' que está a executar esta rotina, e associa o valor obtido a um índex
// turn on LEDs
mask = (60-32)-i;
mask = 1<<mask;
DIRB |= mask;
OUTB &= ~mask;
while(1)
{
flag = flags[i]; // Lê as variáveis "flag"
number = numbers[i]; // e "number" dirigida ao 'cog' que está a executar este procedimento
if (flag) // Se o 'cog' estiver marcado como activo, então inicia o cálculo
{
result = isprime(number); // Calcula se o número dado é primo ou não
results[i] = result; // Devolve o resultado (se é primo ou não)
flags[i] = 0; // Marca o 'cog' como "inactivo"
}
}
}
Although you can see the program code above, the same is also attached. Download and have fun!
Kind regards, Samuel Lourenço
Comments
I tried it with 230400 baud and the output seemed fine. There's no reason that changing the baud rate should affect any calculations. The only difference would be in timing of how COG 0 responds to the other COGs, but there are locks in place for that. Are you sure this is still a problem? If so, how does it appear: is the count of primes incorrect, or are there just missing primes in the output?
Thanks,
Eric
In 73 I assisted in electronic design using one of the most powerful chips of the day - a stand-alone combined Transmit/Receive UART in a 40pin Ceramic chip. My boss and I replaced Telex regenerators that were a paper tape punch to paper tape reader and a short spooler for the paper tape. There were hundreds of these machines at OTC (the overseas part of Telecom in Australia).
But these little programs got me hooked for a minor career change to computers from the start of 74.
Never looked back
I've seen this happening with SimpleIDE on Linux (which, in my case, is the host OS).
Kind regards, Samuel Lourenço