Help optimising a basic C programme. - Cemetech | Forum

Izder456
Member (Posts: 149)

Help optimising a basic C programme.
21 Mar 2020 02:55:54 pm
Last edited by Izder456 on 21 Mar 2020 03:21:54 pm; edited 1 time in total

Hey y'all, izder here, please don't capitalise the "i" as that is how I spelt it when I first came up with it, and it looks a whole lot better that way too...also I messed it up when creating this acct...lol

I translated a basic vanilla C programme here https://codedost.com/c/basic-c-programs/c-program-generate-prime-numbers-upto-n/ ti TI-84CE C, for the heck of it :

Code:

////////////////////////////////////////


// { prgmSEIVEC } { v1.2 }


// Author: izder456


// License: n/a


// Description: generate primes up to n


////////////////////////////////////////





/* Keep these headers */


#include <stdbool.h>


#include <stddef.h>


#include <stdint.h>


#include <tice.h>





/* Standard headers */


#include <math.h>


#include <stdio.h>


#include <stdlib.h>


#include <string.h>





/* Other available headers: stdarg.h, setjmp.h, assert.h, ctype.h, float.h, iso646.h, limits.h, errno.h */





/* uint8_t is an unsigned integer that can range from 0-255. */


/* It performs faster than just an int, so try to use it (or int8_t) when possible */





/* Put function prototypes here */


#define INPUT_SIZE 10


void printText(const char *text, uint8_t x, uint8_t y);





/* Put all your code here */


int main()


{


    int i, j, c, n;


    const char* start = "Till? ";


    char prompt[] = "";


    char *ptr;


    char inputBuffer[INPUT_SIZE];


    char istr[12];





    os_ClrHomeFull();


    printText(start, 0, 0);


    os_GetStringInput(prompt, inputBuffer, INPUT_SIZE);


    n = strtol(inputBuffer, &ptr, INPUT_SIZE);





    os_ClrHomeFull();


    printText("Prime numbers: ", 0, 0);


    printText("", 0, 1);


    for(i=2;i<=n;i++)


    {


        c = 0;


        for(j=1;j<=i;j++)


        {


            if(i%j==0)


            {


                c =  c + 1;


            }


        }





        if(c==2)


        {


            //printf("%d ",i);


            sprintf(istr, "%d ", i);


            os_PutStrFull(istr);


            os_NewLine();


        }


    }





    os_PutStrFull("DONE!");


    while (!os_GetCSC());


    return 0;


}





/* Draw text on the homescreen at the given X/Y cursor location */


void printText(const char *text, uint8_t xpos, uint8_t ypos)


{


    os_SetCursorPos(ypos, xpos);


    os_PutStrFull(text);


}

I've seen it performs a whole lot better than it's TI-BASIC equivalent :

Code:

ClrHome


Prompt N


For(I,2,N,1


 0->C


 For(J,1,I,1


  If (remainder(I,J)=0)


  C+1->C


 End


 If (C=2)


 Disp I


End


Disp "DONE!


Pause

Is there a way to get it running even faster?

I'm looking at you Cemetech hivemind....

MateoConLechuga
2
Official Cemetech Lettuce Manager (Posts: 3937)

21 Mar 2020 02:57:47 pm

There's an example in the toolchain that is what you want, however input is in Ans:
https://github.com/CE-Programming/toolchain/tree/master/examples/fileioc/factorize

Izder456
Member (Posts: 149)

21 Mar 2020 03:00:35 pm

MateoConLechuga wrote:

There's an example in the toolchain that is what you want, however input is in Ans:
https://github.com/CE-Programming/toolchain/tree/master/examples/fileioc/factorize

It doesn't look like is spews out primes like in the ti basic, just returns how many. [ I may be mistaken ].

MateoConLechuga
2
Official Cemetech Lettuce Manager (Posts: 3937)

21 Mar 2020 03:01:50 pm

Izder456 wrote:

MateoConLechuga wrote:

There's an example in the toolchain that is what you want, however input is in Ans:
https://github.com/CE-Programming/toolchain/tree/master/examples/fileioc/factorize

It doesn't look like is spews out primes like in the ti basic, just returns how many. [ I may be mistaken ].

You are mistaken.

Izder456
Member (Posts: 149)

21 Mar 2020 03:02:28 pm

MateoConLechuga wrote:

Izder456 wrote:

MateoConLechuga wrote:

There's an example in the toolchain that is what you want, however input is in Ans:
https://github.com/CE-Programming/toolchain/tree/master/examples/fileioc/factorize

It doesn't look like is spews out primes like in the ti basic, just returns how many. [ I may be mistaken ].

You are mistaken.

mega oof.

MateoConLechuga
2
Official Cemetech Lettuce Manager (Posts: 3937)

21 Mar 2020 03:03:18 pm

Nope I'm mistaken. That example does the factors of a number.

Izder456
Member (Posts: 149)

21 Mar 2020 03:05:21 pm

MateoConLechuga wrote:

Nope I'm mistaken. That example does the factors of a number.

and it crashes the emulated TI84ce :
see here : https://www.dropbox.com/sh/kqpy3t2b6oj2o1x/AABWj-NiimBJSgdftfTfKDc0a?dl=0

Izder456
Member (Posts: 149)

optimised file size
21 Mar 2020 03:46:11 pm
Last edited by Izder456 on 22 Mar 2020 12:19:44 pm; edited 2 times in total

Hey, I got something done!
reformating reduced ~.1kb or ~100bytes

Code:

////////////////////////////////////////


// { prgmSEIVEC } { v1.3 }


// Author: izder456


// License: n/a


// Description: generate primes up to n


////////////////////////////////////////





/* Keep these headers */


#include <stdbool.h>


#include <stddef.h>


#include <stdint.h>


#include <tice.h>





/* Standard headers */


#include <math.h>


#include <stdio.h>


#include <stdlib.h>


#include <string.h>





/* Other available headers: stdarg.h, setjmp.h, assert.h, ctype.h, float.h, iso646.h, limits.h, errno.h */





/* uint8_t is an unsigned integer that can range from 0-255. */


/* It performs faster than just an int, so try to use it (or int8_t) when possible */





/* Put function prototypes here */


#define INPUT_SIZE 10


void printText(const char * text, uint8_t x, uint8_t y);





/* Put all your code here */


int main() {


  int i, j, c, n;


  const char * start = "Till? ";


  char prompt[] = "";


  char * ptr;


  char inputBuffer[INPUT_SIZE];


  char istr[12];





  os_ClrHomeFull();


  printText(start, 0, 0);


  os_GetStringInput(prompt, inputBuffer, INPUT_SIZE);


  n = strtol(inputBuffer, & ptr, INPUT_SIZE);





  os_ClrHomeFull();


  printText("Prime numbers: ", 0, 0);


  printText("", 0, 1);


  for (i = 2; i <= n; i++) {


    c = 0;


    for (j = 1; j <= i; j++) {


      if (i % j == 0) {


        c = c + 1;


      }


    }





    if (c == 2) {


      //printf("%d ",i);


      sprintf(istr, "%d ", i);


      os_PutStrFull(istr);


      os_NewLine();


    }


  }





  os_PutStrFull("DONE!");


  while (!os_GetCSC());


  return 0;


}





/* Draw text on the homescreen at the given X/Y cursor location */


void printText(const char * text, uint8_t xpos, uint8_t ypos) {


  os_SetCursorPos(ypos, xpos);


  os_PutStrFull(text);


}

EDIT :

hey MateoConLechuga,
the base code for pb says this :

Code:

/* uint8_t is an unsigned integer that can range from 0-255. */


/* It performs faster than just an int, so try to use it (or int8_t) when possible */

Is there A way I could use these types in this programme?
unint8_t overflows and crashes when I try
and int8_t is just buggy and doesn't go to "n" primes, when I try

EverydayCode
1
Newbie (Posts: 19)

21 Mar 2020 07:37:04 pm

I've left this thing running for 3 hours, and it's still going!

The limit is 123456...

Izder456
Member (Posts: 149)

21 Mar 2020 07:41:02 pm

EverydayCode wrote:

The limit is 123456...

it should be the integer limit of C on the ez80 [Maybe 2,147,483,647?]

dave1707
Advanced Member (Posts: 182)

24 Mar 2020 11:21:39 am

I ran the above TI-Basic program to calculate the prime numbers up to 1,000 on my TI84+CE. It took 37 minutes and 52 seconds to print the primes to 1,000. Too slow. I wrote the below code to calculate primes and it took 40 seconds to print primes to 1,000. This program uses a list which has a limit of 999 entries. That means I can only calculate primes up to 7,917 which creates 999 primes. I can change the code to use multiple list which would increase the prime count, but why bother when I have an ipad. I modified this code to run on my ipad and I calculated primes to 10,000,000. There were 664,579 primes and it took 10.6 seconds. Just to show the speed difference to calculate primes to 1,000, it took .00025 seconds on the ipad. Thats 160,000 times faster on the TI84+CE for my program and 9,088,000 times faster than the program above.

Code:




2→ʟ1(1):1→P


For(Z,2,1000


√(Z→Q:0→F


For(X,1,P


ʟ1(X)→A


If A>Q:P→X


If remainder(Z,A)=0:Then


1→F:P→X:End


End


If F=0:Then


P+1→P:Z→ʟ1(P):Disp Z:End


End


Disp "TOTAL ",P

Izder456
Member (Posts: 149)

24 Mar 2020 01:16:23 pm

dave1707 wrote:

I ran the above TI-Basic program to calculate the prime numbers up to 1,000 on my TI84+CE. It took 37 minutes and 52 seconds to print the primes to 1,000. Too slow. I wrote the below code to calculate primes and it took 40 seconds to print primes to 1,000. This program uses a list which has a limit of 999 entries]

that's a creative usage of lists! I was looking to optimise the programme in C however....

dave1707
Advanced Member (Posts: 182)

24 Mar 2020 01:49:21 pm

Izder456

Here’s the Lua code I ran on my iPad. It’s not C, but it’s close enough that you can convert it to C and use it to speed up your program. I was a C programmer by profession for many years, so I could probably optimize your code, but then you wouldn’t learn how to do it yourself.

Code:




function setup()


    tab={2}                 -- put 2 in the first position of the table


    p=0


    for z=2,100 do          -- calculate primes to 100


        q=math.sqrt(z)


        f=0                 -- set flag to 0  


        for x=1,p do        -- loop thru all previous primes in the table


            a=tab[x]        -- get number from table


            if a>q then     -- it's greater than square root, stop checking


                break 


            end


            if z%a==0 then  -- divide number with prime from table


                f=1         -- set to 1, number isn't a prime


                break       -- it's not prime, so stop checking


            end


        end


        if f==0 then        -- number wasn't divisible by anything, it's prime


            p=p+1 


            tab[p]=z        -- put prime number in table            


            print(z)        -- print each prime number


        end


    end


end

Izder456
Member (Posts: 149)

24 Mar 2020 04:19:03 pm

dave1707 wrote:

Izder456

Here’s the Lua code I ran on my iPad. It’s not C, but it’s close enough that you can convert it to C and use it to speed up your program. I was a C programmer by profession for many years, so I could probably optimize your code, but then you wouldn’t learn how to do it yourself.

Code:




function setup()


    tab={2}                 -- put 2 in the first position of the table


    p=0


    for z=2,100 do          -- calculate primes to 100


        q=math.sqrt(z)


        f=0                 -- set flag to 0  


        for x=1,p do        -- loop thru all previous primes in the table


            a=tab[x]        -- get number from table


            if a>q then     -- it's greater than square root, stop checking


                break 


            end


            if z%a==0 then  -- divide number with prime from table


                f=1         -- set to 1, number isn't a prime


                break       -- it's not prime, so stop checking


            end


        end


        if f==0 then        -- number wasn't divisible by anything, it's prime


            p=p+1 


            tab[p]=z        -- put prime number in table            


            print(z)        -- print each prime number


        end


    end


end

ok thanks! I'll try to convert it!

Edit :

here's my converted code, however it prints "2" then instantly quits, so it doesn't work.
dave1707, do you know what the problem could be?

Code:

void main(void)


{


    int tab[] = {2};


    int p = 0;


    float q;


    int z;


    int f;


    int a;


    int x;


    char zstr[2];


    for(z=2;z<=100;z++) {


        q=sqrt(z);


        f=0;


        for(x=1;x<=p;x++) {


            a=tab[x];


            if(a>q) {


                break;


            }


            if(z%a==0) {


                f=1;


                break;


            }


        }


        if(f==0) {


            p++;


            z=tab[p];


            sprintf(zstr, "%d", z);


            os_PutStrFull(zstr);


            os_NewLine();


        }


    }


}

dave1707
Advanced Member (Posts: 182)

24 Mar 2020 05:04:43 pm

Izder456 In the If statement near the bottom, you have z=tab[p]. That should be reversed, tab[p]=z. You want to create the table tab with the prime numbers that you find. That way each number that you want to check if it’s prime, you’re only dividing by the prime numbers that have been found so far.

Izder456
Member (Posts: 149)

15 Apr 2020 09:03:03 pm

dave1707 wrote:

Izder456 In the If statement near the bottom, you have z=tab[p]. That should be reversed, tab[p]=z. You want to create the table tab with the prime numbers that you find. That way each number that you want to check if it’s prime, you’re only dividing by the prime numbers that have been found so far.

ok, got that fixed (I also added in input for max value) :

Code:

void main(void)


{


    int tab[] = {};


    int p = 0;


    float q;


    int z;


    int f;


    int a;


    int x;


    int i;


    char zstr[2];


    char * ptr;


    char ques[7] = "Till? ";


    char input[] = "";


    os_ClrHomeFull();


    os_GetStringInput(ques, input, 10);


    i = strtol(input, & ptr, 0);


    for(z=2;z<=i;z++) {


        q=sqrt(z);


        f=0;


        for(x=1;x<=p;x++) {


            a=tab[x];


            if(a>q) {


                break;


            }


            if((z%a)==0) {


                f=1;


                break;


            }


        }


        if(f==0) {


            p++;


            tab[p]=z;


            sprintf(zstr, "%d", z);


            os_PutStrFull(zstr);


            os_NewLine();


        }


    }


}





/* Draw text on the homescreen at the given X/Y cursor location */


void printText(const char *text, uint8_t xpos, uint8_t ypos)


{


    os_SetCursorPos(ypos, xpos);


    os_PutStrFull(text);


}

Now here's the problem, Its just counting not printing prime numbers. This is true for any input.

MateoConLechuga
2
Official Cemetech Lettuce Manager (Posts: 3937)

16 Apr 2020 08:02:03 am

Wtf is "int tab[] = {};"

You need to work on your variable names too.

dave1707
Advanced Member (Posts: 182)

16 Apr 2020 08:58:24 am

What are you doing with zstr. It looks like you’re putting a value of 2 in it and printing that. In the last if statement, the variable z should contain the latest prime number to be printed.

DrDnar
1
Expert (Posts: 520)

16 Apr 2020 11:28:54 am
Last edited by DrDnar on 16 Apr 2020 01:30:48 pm; edited 1 time in total

Oh, no no no, don't run that.

Arrays in C DO NOT dynamically expand on demand like in TI BASIC. That's going to savagely murder your stack.

While you could statically allocate the array:
Code:

int tab[1000];

doing so would be unwise. Stack space on the CE is limited, and due to limitations in Zilog's C compiler, functions suddenly get much slower if they have more than 128 bytes of local variables.

A better option is to use dynamic memory allocation. First, declare tab as an array unbound to any storage:
Code:

int* tab;

(In C, arrays and pointers are syntactically largely interchangeable.) You can then bind dynamic memory to the array like so:
Code:

tab = malloc(arraysize* sizeof(int));


if (tab == NULL) {


   handle_memory_allocation_failure();


}

As before, you can do tab[x] to access member x in tab. Note that memory allocated like this is not initialized, so you should assume the contents of each element in the array are garbage until you overwrite them.

You also have the option of later resizing the array if you wish:
Code:

int* newtab;


. . .


newtab = realloc(tab, newsize * sizeof(int));


if (newtab == NULL) {


   handle_unable_to_expand();


} else {


   tab = newtab;


}

If reallocation fails, tab remains valid, so if you want, you can continue with the old-size tab. Again, the new elements are not initialized. (You can also shrink the array if you want.)

There is a different routine called calloc() that will both allocate memory and initialize all elements of your array to zero:
Code:

tab = calloc(limit, sizeof(int));

However, if you later expand the array using realloc(), the new elements will not be initialized.

The maximum size array you can get using this technique is about 23 thousand ints or about 34 thousand shorts.

Finally, you can also deallocate all memory used by the array:
Code:

free(tab);

The C SDK's runtime will automatically handle this cleanup for you when your program ends. However, if you need to repeatedly allocate temporary storage, failure to free() when you're done with a temporary object will cause a memory leak. Again, that lost memory will be reclaimed once your program ends---but not before!

Also, if the algorithm can run on unsigned integers, you should use unsigned integers. On the eZ80, comparisons (other than == and !=) are slower on signed integers.

Izder456
Member (Posts: 149)

16 Apr 2020 01:05:50 pm

dave1707 wrote:

What are you doing with zstr. It looks like you’re putting a value of 2 in it and printing that. In the last if statement, the variable z should contain the latest prime number to be printed.

im initialising an array with 3 terms, zero being one of them.

MateoConLechuga wrote:

Wtf is int tab[] = {};

Isn't that how do it?

DrDnar wrote:

Arrays in C DO NOT dynamically expand on demand like in TI BASIC. That's going to savagely murder your stack.

ok, got it.

DrDnar wrote:

A better option is to use dynamic memory allocation.

ok, with your suggestions, I came up with this code :

Code:

void main(void)


{


    int* tab;


    tab = malloc(1* sizeof(int));


    int* newtab;


    int p = 0;


    float q;


    int z;


    int f;


    int a;


    int x;


    int i;


    char zstr[2];


    char * ptr;


    char ques[7] = "Till? ";


    char input[] = "";


    free(tab);


    os_ClrHomeFull();


    os_GetStringInput(ques, input, 10);


    i = strtol(input, & ptr, 0);


    for(z=2;z<=i;z++) {


        q=sqrt(z);


        f=0;


        for(x=1;x<=p;x++) {


            a=tab[x];


            if(a>q) {


                break;


            }


            if((z%a)==0) {


                f=1;


                break;


            }


        }


        if(f==0) {


            p++;


            newtab = realloc(&p+1, sizeof(int));


            if (newtab == NULL) {


                os_PutStrFull("Memory Size ERR");


            } else {


                tab = newtab;


            }


            if (tab == NULL) {


                os_PutStrFull("Memory ERR");


            }


            tab[p]=z;


            sprintf(zstr, "%d", z);


            os_PutStrFull(zstr);


            os_NewLine();


        }


    }


}

However, it results in a crash after answering the "Till? " question. This works for any input. What am I doing wrong?

edit :
I changed the int declaration from this :

Code:

int z;


int f;


int a;


int x;


int i;

to this :

Code:

uint16_t z;


uint32_t f;


uint32_t a;


uint32_t x;


uint32_t i;

but...the problem still persists