Prime number calculation program (finally in English)

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.
/*
 * 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
c
c
10K

Comments

  • samuell wrote: »
    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.

    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
    FlexGUI, a GUI for programming the P1 and P2 in Spin, PASM, BASIC, and C.
    Help support its development at Patreon or PayPal.
  • Cluso99Cluso99 Posts: 15,656
    edited 2019-11-17 - 19:56:03
    Brings back memories. That was one of my first programs I wrote while studying Electronics way back in 1972. I had done a few tiny programs at work during training in 70-72.
    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 :)
    My Prop boards: P8XBlade2 , RamBlade , CpuBlade , TriBlade
    P1 Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    P1: Tools (Index) , Emulators (Index) , ZiCog (Z80)
    P2: Tools & Code , Tricks & Traps
  • ersmith wrote: »
    ...
    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
    There are missing lines/characters once in a while, but clearly that is not related to the program itself, or the hardware. I think it is just FlexGUI that can't cope with the serial output and thus skips entire strings. However, note that I'm running FlexGUI inside a VM.

    I've seen this happening with SimpleIDE on Linux (which, in my case, is the host OS).

    Kind regards, Samuel Lourenço
Sign In or Register to comment.