|
I have a couple friends of mine who are learning to program, and I've been helping to teach them about basic uses of pointers. For some reason writing out small practice C programs is really relaxing, so I made a few different small practice programs for my friends. There's some sort of task to achieve with a little framework code written to be used. I tried to write each practice program to focus on one small aspect of pointers or memory management. I want to share them with you guys, as they might help someone and it'd be fun to share solutions.
+ Show Spoiler [PointerPractice_1.c] +#include <stdio.h> /* printf */
/* Prints a specific element within an array. */ void PrintElement( const int *array, const int element ) { /* Place your code here */ /**/ /**/ /**/ /* array is a variable local to only this scope. That means you can modify the pointer array, and change where it points to. It starts by pointing to the first element in the stackArray from main. */ printf( "%d", *array ); }
int main( void ) { /* Create array on the stack. */ int stackArray[] = { 1, 3, 5, 6, 7, 9, 12, 15, 19, 21, 25 }; int arraySize = sizeof( stackArray ) / sizeof( stackArray[0] ); /* Do not modify below this. */ PrintElement( stackArray, 4 ); /* Correct output: 7 */ return 0; } + Show Spoiler [PointerPractice_2.c] +#include <stdio.h> /* printf */ /* Prints a specific element within an array. */ void PrintElement(const int element) { printf("%d, ", element); } /* Prints out contents of an entire array. */ /* MODIFY ONLY THIS FUNCTION. */ void PrintArray(const int *array, const int size) { int x; for (x = 0; x < size; x++) { PrintElement(*array); } } int main(void) { /* Create array on the stack. */ int stackArray[] = { 1, 3, 5, 6, 7, 9, 12, 15, 19, 21, 25 }; int arraySize = sizeof(stackArray) / sizeof(stackArray[0]);
PrintArray(stackArray, arraySize);
/* Correct output: 1, 3, 5, 6, 7, 9, 12, 15, 19, 21, 25, */
return 0; } + Show Spoiler [PointerPractice_3.c] +#include <stdio.h> /* printf */
/* Modify this function's signature. A function's signature is what the function takes as parameters and returns as a value. For this you won't modify the the return value. */ void SwapInts( int a, int b ) { /* Place your code here. Modify these lines. */ int temp = a; a = b; b = temp; } /* Prints a specific element within an array. */ int main(void) { int a = 10; int b = 6; /* Modify this line. */ SwapInts( a, b ); printf("%d, %d", a, b ); /* Correct output: 6, 10 */
return 0; } + Show Spoiler [PointerPractice_4.c] +#include <stdio.h> /* printf */
/* Swap the contents of two pointers. Do not modify the prototype. Use your function from PointerPractice_3 here. */ void SwapInt( ) { }
/* Print contents of an array. Do not modify this function. */ void PrintArray( const int* array, const int size ) { int i; for(i = 0; i < size; ++i, ++array) { if(i != size - 1) printf( "%d, ", *array); else printf( "%d\n", *array); } }
int main( void ) { /* Create array on the stack. */ int stackArray[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; /* Get size of array. stackArray can be treated as pointer to first element. */ int arraySize = sizeof( stackArray ) / sizeof( *stackArray ); /* Can treat name of an array as pointer to first element. */ PrintArray( stackArray, arraySize ); /* Reverse the array here */ /**/ /**/ /**/ PrintArray( stackArray, arraySize ); /* Correct output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 */ return 0; } + Show Spoiler [PointerPractice_5.c] +#include <stdio.h> /* printf */
/* Swap the contents of two pointers. Do not modify the prototype. Use your function from PointerPractice_3 here. */ void SwapInt( ) { }
/* Print contents of an array. Do not modify this function. */ void PrintArray( const int* array, const int size ) { int i; for(i = 0; i < size; ++i, ++array) if(i != size - 1) printf( "%d, ", *array); else printf( "%d\n", *array); }
int main( void ) { /* Create array on the stack. */ int stackArray[] = { 23, 13, 1, 3, 5, 0, 14, 23, 1, 30, 2 }; /* Get size of array. stackArray can be treated as pointer to first element. */ int arraySize = sizeof( stackArray ) / sizeof( *stackArray ); /* Can treat name of an array as pointer to first element. */ PrintArray( stackArray, arraySize ); /* Order the array here */ /**/ /**/ /**/ /* Do not modify below this. */ PrintArray( stackArray, arraySize ); /* Correct output: 23, 13, 1, 3, 5, 0, 14, 23, 1, 30, 2 0, 1, 1, 2, 3, 5, 13, 14, 23, 23, 30 */ return 0; } + Show Spoiler [Concat.c] +#include <stdio.h> // strlen and printf #include <stdlib.h> // malloc and free char *ConcatStrings( const char *str1, const char *str2 ) { /* Place your code here */ /* Starts as a string pointer to the literal "EMPTY STRING". You'll need to use malloc to create a character array and store the pointer malloc returns within concatenated. */ char *concatenated = "EMPTY STRING"; /**/ /**/ /**/ return concatenated; } int main( void ) { const char string1[] = "Concat with me to make "; const char string2[] = "a conjoined sentence."; char *concatenatedString = ConcatStrings( string1, string1 ); printf( "String after concatentation: %s", concatenatedString ); return 0; } + Show Spoiler [WordSort.c] +#include <stdio.h> /* printf, scanf */ #include <string.h> /* strlen, strcpy */ #include <stdlib.h> /* malloc, free */
/* Grow an array. */ void GrowArray( char ***array, int size, int *capacity ) { int i; /* for looping */ int newCapacity = (*capacity) ? *capacity * 2 : 1; /* Allocate memory twice the size of the previous capacity. Allocate one if the capacity is zero. Don't forget to multiply the capacity to allocate by the size of a char * in byes. */ char **temp = (char **)malloc( newCapacity * sizeof( char * ) ); printf( " CALLED: GrowArray : size %d; *capacity %d; new capacity %d\n", size, *capacity, newCapacity); /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } /* Update capacity to reflect size of the temp's allocation. */ *capacity = newCapacity; /* Free the old array. */ if(*array) free( *array ); /* Make the array point to the location we allocated. */ *array = temp; }
/* Dynamically allocate a string, copy the contents of toCopy into it, and then return the dynamically allocated string. */ char *CopyString( const char *toCopy ) { char *temp = (char *)malloc( strlen( toCopy + 1 ) * sizeof( char ) ); strcpy( temp, toCopy ); return temp; }
/* Print out a char array. */ void PrintCharArray( const char **array, int length ) { int i; printf( " PrintCharArray( ):\n" ); for(i = 0; i < length; ++i) printf( " -%s\n", array[i] ); }
int main( void ) { /* Create a pointer to character pointer with address initialized to zero. */ char **words = { 0 }; int size = 0; int capacity = 0; int i; /* for looping */ /* Use this to gather input. No words over length of twenty. Initialize array to zero. */ char input[21] = { 0 }; printf( "Please enter strings followed by enter. Hit enter without a string to" " end the program.\n" ); /* Infinite loop. */ for(;;) { printf( " " ); /* Get input string. */ gets( input ); /* Only add it to the array if user didn't just hit enter without inputting a string. */ if(*input != '\0') { ++size; /* Grow array if we need more space. */ if(size > capacity) GrowArray( &words, size, &capacity ); /* Copy our input string into the words array. */ words[size - 1] = CopyString( input ); } /* While a string with '\0' (user presses enter) in front is not found. */ else break; } /* SORT THE ARRAY OF WORDS HERE IN ALPHABETICAL ORDER */ /**/ /**/ /**/ PrintCharArray( (const char**)words, size ); free( words ); return 0; }
They should be written from easiest to hardest. I don't have solutions for all of them, but I can write one in if anyone needs to see a solution. Anyways, feel free to post up your solutions it'd be fun to share them. Also feel free to ask questions
Look for this thing to see where you code is intended to go:
/* Place your code here */ /**/ /**/ /**/
As for the next practice program I think I'll be doing something with function pointers. The last program is mimicking a C++ vector with a few loose variables, but making it into an object with structs + function pointers would be cool. Jump tables and vtables are pretty sweet and it'd be fun to mess around with them.
|
thedeadhaji
39473 Posts
For some reason writing out small practice C programs is really relaxing
I know what you mean. I received a new tail light for my bike today, and I was going through the various modes of the device, I caught myself thinking, "man, programming the MCU to do this would be pretty fun" (fun b/c it's simple and readily rewarding)
|
i really despise coding stuff in C, but in general i preffer functional programming. most of these assignments seem fairly suited for people who havent done C tho
|
!dontcastmalloc
'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial
|
This part in wordsort.c confuses me:
[...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..?
|
On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Yes
http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc
But for the purposes of a teaching a first year some basic pointer stuff, it's probably ok to include ugly hack code in the parts they're not even going to be modifying.
|
On November 03 2012 11:02 Khalum wrote:This part in wordsort.c confuses me: [...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..?
well, it's especially nonsensical since the c standard defines that no action is taken if free receives a null pointer.
|
On November 03 2012 11:12 uberMatt wrote:Show nested quote +On November 03 2012 11:02 Khalum wrote:This part in wordsort.c confuses me: [...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..? well, it's especially nonsensical since the c standard defines that no action is taken if free receives a null pointer.
True!
[edit] my excuse: it's past 3am
|
On November 03 2012 11:02 Khalum wrote:This part in wordsort.c confuses me: [...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..? The for loop doesn't run if the pointer is null. As for not passing null to free, I was just being explicit with how the flow of the function works.
On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Casting the pointer is something I've been taught to do. It's a pretty minor detail that really comes down to personal preference.
|
On November 03 2012 11:27 CecilSunkure wrote: [..] The for loop doesn't run if the pointer is null. As for not passing null to free, I was just being explicit with how the flow of the function works. [..]
What prevents me from doing this?
[..] char **array= 0; int capacity = 0; GrowArray( &array, 10, &capacity ); [..]
|
On November 03 2012 11:44 Khalum wrote:Show nested quote +On November 03 2012 11:27 CecilSunkure wrote: [..] The for loop doesn't run if the pointer is null. As for not passing null to free, I was just being explicit with how the flow of the function works. [..]
What prevents me from doing this? [..] char **array= 0; int capacity = 0; GrowArray( &array, 10, &capacity ); [..]
Right but it's assumed you don't modify the existing code unless told to. In the op I was talking about putting that stuff into a nice object making use of function pointers as an exercise.
|
On November 03 2012 11:27 CecilSunkure wrote:Show nested quote +On November 03 2012 11:02 Khalum wrote:This part in wordsort.c confuses me: [...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..? The for loop doesn't run if the pointer is null. As for not passing null to free, I was just being explicit with how the flow of the function works. Show nested quote +On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Casting the pointer is something I've been taught to do. It's a pretty minor detail that really comes down to personal preference.
yeah, i understand. but i think that someone new to c might reasonably conclude that function arguments should be cast with the const keyword due to the code examples, not realizing that they are superfluous. i think that the first few tutorials that people do when they start programming or learning a new language have a large effect on their future thought process when writing programs, so it is important to make sure that everything is logical and does not give the wrong impression.
|
On November 03 2012 12:02 uberMatt wrote:Show nested quote +On November 03 2012 11:27 CecilSunkure wrote:On November 03 2012 11:02 Khalum wrote:This part in wordsort.c confuses me: [...] /* Copy contents into temp. */ for(i = 0; i < size - 1; ++i) { temp[i] = (*array)[i]; } [...] /* Free the old array. */ if(*array) free( *array ); [...]
The if(*array) is basically nonsense as the for loop would have crashed anyways if the array was a null pointer..? The for loop doesn't run if the pointer is null. As for not passing null to free, I was just being explicit with how the flow of the function works. On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Casting the pointer is something I've been taught to do. It's a pretty minor detail that really comes down to personal preference. yeah, i understand. but i think that someone new to c might reasonably conclude that function arguments should be cast with the const keyword due to the code examples, not realizing that they are superfluous. i think that the first few tutorials that people do when they start programming or learning a new language have a large effect on their future thought process when writing programs, so it is important to make sure that everything is logical and does not give the wrong impression. Ah yeah, if you want you can modify it and post it up. I can take a look a probably swap it out.
|
By the time I get done programming all day at work I am too burned out to do any personal exploration of CS related things
|
On November 03 2012 10:45 ragnorr wrote: i really despise coding stuff in C, but in general i preffer functional programming. most of these assignments seem fairly suited for people who havent done C tho woo yeah functional programming!
i like C sometimes though
|
Yeah same here when you program most of the day its a little harder to sit down and program just for fun. I cant look at code outside of work really anymore. Its just too much time looking at a computer really and sitting down. It is fun though if its just a hobby kind of thing for school.
|
int a[1]; int b[1][1]; int *c; int **d; int *e[]; int *f[0];
Okay for 100 points each, what happens at each line (what value is stored, or what error is produced)?
*a = 5; b = &a; *c = 5; d = f; e[0] = c; f = d;
|
United States10328 Posts
lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.)
Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...]
|
On November 03 2012 11:27 CecilSunkure wrote: Casting the pointer is something I've been taught to do. It's a pretty minor detail that really comes down to personal preference.
It's awesome if your compiler predates the 1989 ANSI C standard, where an entire type was invented to avoid having that cast in there.
|
On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
|
On November 03 2012 11:07 phar wrote:Show nested quote +On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Yes http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-mallocBut for the purposes of a teaching a first year some basic pointer stuff, it's probably ok to include ugly hack code in the parts they're not even going to be modifying. Actually it's pretty problematic if you show beginners bad code. They might think it's the right way to do it.
|
On November 03 2012 21:22 spinesheath wrote:Show nested quote +On November 03 2012 11:07 phar wrote:On November 03 2012 11:00 uberMatt wrote:!dontcastmalloc 'const' in c and c++ are fundamentally different, you might want to look up the difference before writing a c tutorial Yes http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-mallocBut for the purposes of a teaching a first year some basic pointer stuff, it's probably ok to include ugly hack code in the parts they're not even going to be modifying. Actually it's pretty problematic if you show beginners bad code. They might think it's the right way to do it. Always 10 times as much time spent on the pedagogy of pointers and type-casting (How its best taught, how to best assist students in not developing bad habits and unexpected behavior headaches) than on the learning. I enjoyed the challenges, for one. Frankly, an investigation into the superfluous steps and the extent to which they assist readability is helpful for any student regardless. Anyone even surprised this is how Cecil was taught it?
|
United States10328 Posts
On November 03 2012 20:28 ragnorr wrote:Show nested quote +On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
yep, I realized that
|
now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5
|
On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C.
|
On November 03 2012 20:28 ragnorr wrote:Show nested quote +On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
Obv you guys should swap like:
void swapInt (int *a, int *b) { *a += *b; *b = *a - *b; *a = *a - *b; } SAVE THAT STACK SPACE.
|
On November 04 2012 06:48 teamamerica wrote:Show nested quote +On November 03 2012 20:28 ragnorr wrote:On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
Obv you guys should swap like: void swapInt (int *a, int *b) { *a += *b; *b = *a - *b; *a = *a - *b; } SAVE THAT STACK SPACE.
Lol. That works, but you might as well use some bit ops instead. That however doesn't work with data types that don't support the minus operator like that.
|
Ya this or even XOR swap is useless but still a fun question to ask people lol. Also this will die with larger numbers but anyway.
You should use swap with a temp. variable in almost any situation I can think of and not try to get in the way of compilers today ^_^
|
On November 04 2012 04:15 CecilSunkure wrote:Show nested quote +On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C.
I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver?
I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++.
** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it.
|
On November 04 2012 07:25 Lysenko wrote:Show nested quote +On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. Everyone at my university learns C and then C++. I myself took it a bit further and started mimicking C++ features in C before I swapped to C++. It's just another way of learning.
Edit: So for example if I were to have someone make a struct object and mimic C++ vtables and inheritance, they could learn a whole lot about how C++ works as well as solidify and understanding of memory management at a low level.
|
On November 04 2012 06:48 teamamerica wrote:Show nested quote +On November 03 2012 20:28 ragnorr wrote:On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
Obv you guys should swap like: void swapInt (int *a, int *b) { *a += *b; *b = *a - *b; *a = *a - *b; } SAVE THAT STACK SPACE.
I like this for saving stack space:
void swapInt (int *a, int *b) { register int c;
c = *b; *b = *a; *a = c; }
(Although, most modern compilers will use a register for c at most optimization levels even if you leave the keyword out, and others ignore the keyword and do what they want.)
Edit: This has the advantage that you can easily replace "int" with "unsigned int" and get good results. The addition/subtraction trick is clever, but whether you can get away with it with unsigned ints is probably implementation-dependent.
|
On November 04 2012 07:32 CecilSunkure wrote: Everyone at my university learns C and then C++. I myself took it a bit further and started mimicking C++ features in C before I swapped to C++. It's just another way of learning.
That's cool. This is like full blast-from-the-past mode for me.
Edit: I don't know that I agree with teaching C to people relatively new to software development so early. It's a language that's so detail-oriented and mistake-prone that the fiddly details inhibit people getting to the bigger concepts of what they're trying to do.
However, if you want to select out the people with the most potential for future success as cutting-edge software engineers, it might be a decent scheme to find them. More so than using Java as a first language, which many schools do.
|
|
On November 04 2012 07:32 Lysenko wrote:Show nested quote +On November 04 2012 06:48 teamamerica wrote:On November 03 2012 20:28 ragnorr wrote:On November 03 2012 18:17 ]343[ wrote:lol, initially for #3 I did + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; a = b; b = &temp; }
but of course that didn't work for #4 (since it doesn't actually swap the contents of the pointers... though I don't think #3 made that clear.) Also wtf in-place n log n sorting algorithms are way harder than expected [except heapsort I guess...] You aint exchanging the value the pointer points to. It should look like this + Show Spoiler + void swapInt(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
Obv you guys should swap like: void swapInt (int *a, int *b) { *a += *b; *b = *a - *b; *a = *a - *b; } SAVE THAT STACK SPACE.
I like this for saving stack space: void swapInt (int *a, int *b) { register int c;
c = *b; *b = *a; *a = c; }
(Although, most modern compilers will use a register for c at most optimization levels even if you leave the keyword out, and others ignore the keyword and do what they want.) Edit: This has the advantage that you can easily replace "int" with "unsigned int" and get good results. The addition/subtraction trick is clever, but whether you can get away with it with unsigned ints is probably implementation-dependent.
Hmm I guess given your background in embedded (and older compilers) you've actually had a need to do this but it seems strange to me because 1) you're not calling 'c' often which is the reason I've read you apply register for 2) register is just a hint and doesn't guarantee anything 3) this might move a variable that's actually being called often out of a register 3) compilers are smarter and will handle this for you anyway (all my c knowledge comes from bruce eckel thinking in c++, but I know that even in c, register doesn't promise anything).
|
On November 04 2012 07:50 teamamerica wrote: Hmm I guess given your background in embedded (and older compilers) you've actually had a need to do this but it seems strange to me because 1) you're not calling 'c' often which is the reason I've read you apply register for 2) register is just a hint and doesn't guarantee anything 3) this might move a variable that's actually being called often out of a register 3) compilers are smarter and will handle this for you anyway (all my c knowledge comes from bruce eckel thinking in c++, but I know that even in c, register doesn't promise anything).
Generally, I agree with each of your points. I consider what I posted as academic an exercise as using adds-and-subtracts, because neither one makes for maintainable code, and while stack space can be at a premium sometimes, one int is rarely a make or break issue (even when you have a hard limit of 32k or less of stack space, as you do in some embedded applications.)
In embedded applications, though, a few things work differently than you might expect. First, if you are working with extremely limited stack space or RAM, as is often the case, you'll probably rely on disabling optimizations for critical code so that you get very predictable results at the machine level, and use compiler extensions that can directly force a variable into a particular register. GNU C has these, for example. Compiler optimization is fantastic, but if you're trying to put exactly the right bit in the right place you can sometimes find your intentions completely optimized out of the code if you're not careful.
One strategy I've seen used in embedded applications is to reserve a couple of registers for use as short-term temporary variable space, then manually assign a variable like c (in this example) to one of them for the duration of the function. Of course, doing something like that means that you have to make rules for yourself like "don't assume that value will be valid across a function call."
Also, for this particular function, in an embedded application, I'd look to see whether the processor itself has an instruction for swapping two values in main memory, or maybe a swap to accumulator function (an accumulator being a register on some processors that's specifically designated as such short-term temporary storage, possibly with special instruction support compared to other registers.) If so, implementing that function in assembly code might make sense.
For just about all the other cases out there, particularly if you're letting the compiler optimize freely, I'd just go ahead and use the code I posted, probably with the "register" keyword omitted. I might also consider defining the function with the "inline" keyword, which should allow the code to be better optimized where it's convenient and less optimized where it's not, particularly if a global optimizer is in use.
Edit: Mostly, optimizations don't really matter that much unless you're focusing on a small bit of code that takes up most of your application's processing time. Usually, in embedded situations, you'd want to pick and choose optimizations, because some optimize for space, and some for speed, and often getting your generated machine code smaller is more important than making it faster, to fit on an EPROM for instance. That would be an example where using "inline" might be a huge mistake.
|
On November 04 2012 07:33 Lysenko wrote:Show nested quote +On November 04 2012 07:32 CecilSunkure wrote: Everyone at my university learns C and then C++. I myself took it a bit further and started mimicking C++ features in C before I swapped to C++. It's just another way of learning. That's cool. This is like full blast-from-the-past mode for me. Edit: I don't know that I agree with teaching C to people relatively new to software development so early. It's a language that's so detail-oriented and mistake-prone that the fiddly details inhibit people getting to the bigger concepts of what they're trying to do. However, if you want to select out the people with the most potential for future success as cutting-edge software engineers, it might be a decent scheme to find them. More so than using Java as a first language, which many schools do. I'm always hearing about how poor graduates are that learn at "java schools" from a lot of respectable people, including current Microsoft employees and other industry veterans. Everyone here that learns by hitting the ground running in C seems to do very well once they've graduated. Seeing my school's alumni success makes it only natural for myself to advocate the same learning style.
As for the detail oriented ways of C, I feel the little fiddly details are things need to be mastered before anything else. When we started learning there weren't "bigger concepts" at all. The fundamentals were the concepts, so nothing was missed.
|
On November 04 2012 08:14 CecilSunkure wrote: As for the detail oriented ways of C, I feel the little fiddly details are things need to be mastered before anything else. When we started learning there weren't "bigger concepts" at all. The fundamentals were the concepts, so nothing was missed.
I've heard the same things too about the use of Java at some schools.
I think my point may not have been clear about the issues with C as a first language. The "fiddly details" in C are mainly either syntactic elements that make the code difficult to read and bugs difficult to locate, or completely manual memory management. Neither of these aid, for example, teaching skills like structured programming, algorithms, or data structures.
For those two specific reasons, using C shields the student from too little, using Java shields them from too much. The possible benefit to using C is that the more talented students will enjoy the extra details even if they're extraneous to what you're trying to teach.
Anyway, the success post-graduation of a CS program is far more determined by the students the school admits than by any curriculum choice.
Interestingly, MIT, Caltech, and Harvey Mudd College (where Day[9], qxc, and I went) have all switched to using Python for their introductory computer science classes.
Apologies for getting off-topic.
Edit: I suspect top schools are moving to Python because it in one stroke eliminates the problem of good students not turning in homework over a misplaced semicolon they can't locate.
|
I will learn C next semester, so I will check this out then! Thanks a lot!
|
after having to do tracing in my c programming class probably a year ago...
I really really ...
REALLY HATE pointers lol
(now I just program random scripts in python...)
|
United States10328 Posts
On November 04 2012 07:10 teamamerica wrote: Ya this or even XOR swap is useless but still a fun question to ask people lol. Also this will die with larger numbers but anyway.
You should use swap with a temp. variable in almost any situation I can think of and not try to get in the way of compilers today ^_^
Hmm, shouldn't XOR swap work in basically all cases? o.o
|
On November 04 2012 07:25 Lysenko wrote:Show nested quote +On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C.
That's no reason to start with C as your first language though.
|
Hijacking this thread for a little bit: When I'm done with High School I have a couple of months vacation and I'd like to teach myself how to program. Iit seems like a very useful skill and like something I would enjoy doing. With what language should I start? And I assume once you have learnt one, the others are easier to learn?
|
On November 04 2012 18:06 Recognizable wrote: Hijacking this thread for a little bit: When I'm done with High School I have a couple of months vacation and I'd like to teach myself how to programme. Iit seems like a very useful skill and like something I would enjoy doing. With what language should I start? And I assume once you have learnt one, the others are easier to learn?
I've recently learnt programming myself, and I would recommend two things: 1. A steep learning curve, but learning it properly: starting with C then going to C++ 2. An easy language that can be useful, and can certainly teach you how programming works: Python
You can learn the latter one on www.codecademy.org
It's easier to start with Python, but I think you learn it a lot better if you just start with C. (this is what professors at my university says, but our classes start with Python)
|
You aren't doing yourself any favors by starting with C. You're most likely not even going to learn how to code properly in C. Start with C# or Java but make sure you learn about reference types and value types.
|
I say start with Python. As I mentioned above, the top tech schools are using it, a lot of the details resemble other more challenging languages, but you'll be building fun stuff a lot faster with it and it has significant value in the real world once you get out of school.
That said, if you're learning for yourself, do whatever sounds like fun!! Learn C, or hell, learn your favorite processor's assembler code. My own path went from Fortran to Applesoft Basic to Apple Pascal to 6502 assembler to Ada (which is what advanced CS students were learning at Harvey Mudd when I started in 1987) to Object Pascal to 68000 assembler to C to C++ to Perl to Objective C to Java to Python. Basically I just learned whatever was convenient and worked well on the platform I had available at any given time to let me do something fun.
It's worth trying out a range of languages, though. They differ in what they do well and it will make new languages easier to pick up. That said, Python is still an awesome place to start these days, it's pretty modern, works on just about any computer, and is very quick to get started with.
|
If you want little programming exercises to learn a new language, I recommend using Project Euler (http://projecteuler.net/http://projecteuler.net/). It's a set of problems that can be solved in any language you want, and once you solve each one you get access to a "forum" discussing the different solutions in different languages for that problem. Really cool.
|
On November 04 2012 17:29 spinesheath wrote:Show nested quote +On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though.
Sure, I agree, but the first language question is what I was getting at.
|
On November 04 2012 17:29 spinesheath wrote:Show nested quote +On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though.
how about if I work on really low-footprint embedded applications where it's the only option, and also the only plausible option?
C is beautiful because it lets you in on what it's doing at a low level. It lets you abstract things *enough* to make good designs, but not so much that you trade all your performance for elegance.
I'm sure lots of companies are developing new code from scratch right now, because cheap mass-produced CPUs don't tend to run lisp interpreters and stuff. For many people in the 'modern' CS/programming world, C will be the "hardest" language they learn that anyone in industry cares about...that's a good reason to learn it if you want to work as a generalist. If you're more interested in pursuing your own projects, or doing something in academia, you can be much more selective about what you learn (i.e. stack-based, functional, etc.. language types).
|
Hey, if you like C, it's cool, I'm not one to judge. But what about the children? What do you think all this glorification of C is going to lead them to? What's next, I'll tell you what's next, those kids are going to grow up thinking that C is OK, and that undermines the core of our society, which is getting things done.
Look at me, I started out with c because of peer pressure. Now I earned the right to say that really made me understand how things really work. Except it didn't. What it did do instead was making everything mind-numbingly tedious so that I never could actually do anything worthwhile - but I was too stubborn to drop it for a long while because after all that's the way real men write code. Don't be me, pick up the tool that you need for the job, and I guarantee you when you actually want to do something for which C is actually the best tool, it won't be any harder to learn. Plus at that point you might even not have given up already.
|
On November 04 2012 21:27 Lysenko wrote: I say start with Python. As I mentioned above, the top tech schools are using it, a lot of the details resemble other more challenging languages, but you'll be building fun stuff a lot faster with it and it has significant value in the real world once you get out of school.
That said, if you're learning for yourself, do whatever sounds like fun!! Learn C, or hell, learn your favorite processor's assembler code. My own path went from Fortran to Applesoft Basic to Apple Pascal to 6502 assembler to Ada (which is what advanced CS students were learning at Harvey Mudd when I started in 1987) to Object Pascal to 68000 assembler to C to C++ to Perl to Objective C to Java to Python. Basically I just learned whatever was convenient and worked well on the platform I had available at any given time to let me do something fun.
It's worth trying out a range of languages, though. They differ in what they do well and it will make new languages easier to pick up. That said, Python is still an awesome place to start these days, it's pretty modern, works on just about any computer, and is very quick to get started with.
I guess I'll start with Python and maybe Java(because I already spent an hour messing around with that). Why are there so many different programming languages anyway? I'm learning for myself, I don't plan on studying Computer Science, probably gonna study Physics. But I've always found it interesting for some reason so I'd like to give it a shot.
|
On November 05 2012 03:00 Recognizable wrote:Show nested quote +On November 04 2012 21:27 Lysenko wrote: I say start with Python. As I mentioned above, the top tech schools are using it, a lot of the details resemble other more challenging languages, but you'll be building fun stuff a lot faster with it and it has significant value in the real world once you get out of school.
That said, if you're learning for yourself, do whatever sounds like fun!! Learn C, or hell, learn your favorite processor's assembler code. My own path went from Fortran to Applesoft Basic to Apple Pascal to 6502 assembler to Ada (which is what advanced CS students were learning at Harvey Mudd when I started in 1987) to Object Pascal to 68000 assembler to C to C++ to Perl to Objective C to Java to Python. Basically I just learned whatever was convenient and worked well on the platform I had available at any given time to let me do something fun.
It's worth trying out a range of languages, though. They differ in what they do well and it will make new languages easier to pick up. That said, Python is still an awesome place to start these days, it's pretty modern, works on just about any computer, and is very quick to get started with. I guess I'll start with Python and maybe Java(because I already spent an hour messing around with that). Why are there so many different programming languages anyway? I'm learning for myself, I don't plan on studying Computer Science, probably gonna study Physics. But I've always found it interesting for some reason so I'd like to give it a shot. A lot of it is due to history. The first languages were obviously very close to machine code, see Assembler. Then slowly people started to realize that they could introduce higher levels of abstraction (like C, C++, C#) to make programming easier, faster (as in the time spent on writing code), and less error prone. A lot of languages were developed to represent the increasing levels of abstraction as time went on and innovations in computer science came up. Computer science is still fairly young, there will still be lots of development which will lead to new languages which support concepts that would be hard to express in other languages (technically you can emulate the stuff in C++ or C# with C, but it's a LOT more work).
Then there are languages which were developed to make programming in a certain environment easy.
Lately we've seen a rise of functional programming languages which represent the logical/mathematical approaches more closely.
The upcoming languages will probably mostly try to deal with the increasing hardware parallelism, which isn't really handled natively in any of the current mainstream languages. Ideally the compiler would produce good parallel code without the programmer having to worry about it at all. Right now you always have to do some work to get your programs to run efficiently on multiple threads.
|
I don't remember pointer intricacies D: Props to those few of you that do this stuff in spare time.
|
Personally I think C++ is way worse as a first language than C, but that's just me. I would go for Python, to start out and then move to Java or C and teach them about memory and pointers and all that good stuff. It's important to know for sure but when just starting out it only gets in the way. When starting out I think it's really important to be able to do interesting things quickly and easily.
|
On November 05 2012 03:00 Recognizable wrote:Show nested quote +On November 04 2012 21:27 Lysenko wrote: I say start with Python. As I mentioned above, the top tech schools are using it, a lot of the details resemble other more challenging languages, but you'll be building fun stuff a lot faster with it and it has significant value in the real world once you get out of school.
That said, if you're learning for yourself, do whatever sounds like fun!! Learn C, or hell, learn your favorite processor's assembler code. My own path went from Fortran to Applesoft Basic to Apple Pascal to 6502 assembler to Ada (which is what advanced CS students were learning at Harvey Mudd when I started in 1987) to Object Pascal to 68000 assembler to C to C++ to Perl to Objective C to Java to Python. Basically I just learned whatever was convenient and worked well on the platform I had available at any given time to let me do something fun.
It's worth trying out a range of languages, though. They differ in what they do well and it will make new languages easier to pick up. That said, Python is still an awesome place to start these days, it's pretty modern, works on just about any computer, and is very quick to get started with. I guess I'll start with Python and maybe Java(because I already spent an hour messing around with that). Why are there so many different programming languages anyway? I'm learning for myself, I don't plan on studying Computer Science, probably gonna study Physics. But I've always found it interesting for some reason so I'd like to give it a shot.
Go Python or Matlab imo. Both you might use for doing physics work anyway later. They both allow you to skip the intro to methods before learning variables, and both let you get stuff done quickly. I don't see a reason to learn Java if you're going to work on Python - just focus on that (if that's the one you like).
|
On November 04 2012 18:06 Recognizable wrote: Hijacking this thread for a little bit: When I'm done with High School I have a couple of months vacation and I'd like to teach myself how to program. Iit seems like a very useful skill and like something I would enjoy doing. With what language should I start? And I assume once you have learnt one, the others are easier to learn? I'm currently teaching myself Cplusplus (phone doesn't have plus sign lol). It's not that bad at least so far. Been only 4 days and in still at basics. I am learning from a set of tutorials by a guy named Bucky who's really good at explaining it. If you want a link or something let me know. I know everytime I have asked what language to start out with most say C#. I would recommend not C as it gives you bad habits. I know multiple books when I was younger always said not to start C as it gives really bad habits and forums. If you want links let me know!
|
On November 04 2012 21:38 kirika80 wrote:If you want little programming exercises to learn a new language, I recommend using Project Euler ( http://projecteuler.net/http://projecteuler.net/). It's a set of problems that can be solved in any language you want, and once you solve each one you get access to a "forum" discussing the different solutions in different languages for that problem. Really cool. I just solved the first 2 in R. The third one looks really hard. How do you find the biggest prime factor of a large number in under a minute?
http://projecteuler.net/problem=3
I hate you. Now I'm going to be thinking about it. I could do the problem with a list of prime factors going up to the square root of the number in question, but other than that I see no way of solving the problem in under a minute.
Finding prime numbers in and of itself is not easy to do. The only way I know how is to use sieve method. But that takes ungodly amounts of time.
For all I know the largest prime of 600851475143 is 775143. I could easily check if 775143 is a prime but even if it wasn't, I'd then have to check if 775141 was a prime. FUCK
I would not recommend learning a language with these exercises. They're meant for masochists, not for learning languages.
Is that how you do the question? With a list. Dumb question doesn't say what I can use. Actually, no, I can do it with sieve. nvm.
|
On November 05 2012 13:09 obesechicken13 wrote:Show nested quote +On November 04 2012 21:38 kirika80 wrote:If you want little programming exercises to learn a new language, I recommend using Project Euler ( http://projecteuler.net/http://projecteuler.net/). It's a set of problems that can be solved in any language you want, and once you solve each one you get access to a "forum" discussing the different solutions in different languages for that problem. Really cool. I just solved the first 2 in R. The third one looks really hard. How do you find the biggest prime factor of a large number in under a minute? http://projecteuler.net/problem=3I hate you. Now I'm going to be thinking about it. I could do the problem with a list of prime factors going up to the square root of the number in question, but other than that I see no way of solving the problem in under a minute. Finding prime numbers in and of itself is not easy to do. The only way I know how is to use sieve method. But that takes ungodly amounts of time. For all I know the largest prime of 600851475143 is 775143. I could easily check if 775143 is a prime but even if it wasn't, I'd then have to check if 775141 was a prime. FUCK I would not recommend learning a language with these exercises. They're meant for masochists, not for learning languages. Is that how you do the question? With a list. Dumb question doesn't say what I can use.
Biggest prime factor is not difficult.
Do something like
for (int i = 2; i * i <= number; i++) { while (i%number == 0) { number = number / i; } }
printf("The greatest prime factor is %d\n", number);
I haven't tested this, but I've coded something similar recently. It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]
Two improvements that could be made: 1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop 2) Code a case to check for divisibility of 2's, since all even divisors are divisible by two. Then you can modify the loop to start like: for (int i = 3; i < number * number; i = i + 2)
This makes it around twice as fast since you are only checking for positive odd real numbers, instead of all positive reals
Your output can be verified at wolfram alpha
http://www.wolframalpha.com/input/?i=prime factors of 600851475143
|
1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire.
It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2.
|
On November 05 2012 13:25 obesechicken13 wrote:Show nested quote +1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire
How about I make you a deal.
I'll teach you primality tests, and you split me half the million dollars
|
On November 05 2012 13:25 obesechicken13 wrote:Show nested quote +1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire. Show nested quote +It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2.
I'm not trolling.
Since the algorithm divides, it will come up with the answer pretty fast. The factors are 2^63, and every pass will divide it by 2. Meaning the loop only needs to run 63 times.
The problem occurs when you have a huge jump, like the first prime factor is like 6,000,000,000+ or so.
|
On November 05 2012 13:31 frogmelter wrote:Show nested quote +On November 05 2012 13:25 obesechicken13 wrote:1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire. It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2. I'm not trolling. Since the algorithm divides, it will come up with the answer pretty fast. The factors are 2^63, and every pass will divide it by 2. Meaning the loop only needs to run 63 times. The problem occurs when you have a huge jump, like the first prime factor is like 6,000,000,000+ or so. Ok. well you seem to know more than I gave you credit for then.
I'm not sure if it is possible to prove if a(any) number that large is prime in 5 seconds. I just heard from wikipedia that:
There is no known useful formula that yields all of the prime numbers and no composites.
http://en.wikipedia.org/wiki/Prime_number
|
On November 05 2012 13:35 obesechicken13 wrote:Show nested quote +On November 05 2012 13:31 frogmelter wrote:On November 05 2012 13:25 obesechicken13 wrote:1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire. It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2. I'm not trolling. Since the algorithm divides, it will come up with the answer pretty fast. The factors are 2^63, and every pass will divide it by 2. Meaning the loop only needs to run 63 times. The problem occurs when you have a huge jump, like the first prime factor is like 6,000,000,000+ or so. Ok. well you seem to know more than I gave you credit for then. I'm not sure if it is possible to prove if a(any) number that large is prime in 5 seconds. I just heard from wikipedia that: Show nested quote +There is no known useful formula that yields all of the prime numbers and no composites. http://en.wikipedia.org/wiki/Prime_number
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
Try that test
And yes, wikipedia is correct. What we are doing is a smarter brute force approach. At best we can try to mitigate the worst case run times, but there are some cases where the run time for the particular algorithm I posted will be O(sqrt(n)/2), which in some cases is still too high
|
On November 05 2012 13:36 frogmelter wrote:Show nested quote +On November 05 2012 13:35 obesechicken13 wrote:On November 05 2012 13:31 frogmelter wrote:On November 05 2012 13:25 obesechicken13 wrote:1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire. It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2. I'm not trolling. Since the algorithm divides, it will come up with the answer pretty fast. The factors are 2^63, and every pass will divide it by 2. Meaning the loop only needs to run 63 times. The problem occurs when you have a huge jump, like the first prime factor is like 6,000,000,000+ or so. Ok. well you seem to know more than I gave you credit for then. I'm not sure if it is possible to prove if a(any) number that large is prime in 5 seconds. I just heard from wikipedia that: There is no known useful formula that yields all of the prime numbers and no composites. http://en.wikipedia.org/wiki/Prime_number http://en.wikipedia.org/wiki/Miller–Rabin_primality_testTry that test No. Good night. I'll do sieve when I feel like it in the future.
|
On November 05 2012 13:37 obesechicken13 wrote:Show nested quote +On November 05 2012 13:36 frogmelter wrote:On November 05 2012 13:35 obesechicken13 wrote:On November 05 2012 13:31 frogmelter wrote:On November 05 2012 13:25 obesechicken13 wrote:1) Code a case to check if it is a prime number to begin with. If it isn't, then enter the loop If I could do this I'd be a millionaire. It can find the prime factors of 9,223,372,036,854,775,808 pretty fast [sub 5 seconds]. Lol. I don't know if you're trolling or if you misunderstand the problem. But That number above has only one prime factor: 2. I'm not trolling. Since the algorithm divides, it will come up with the answer pretty fast. The factors are 2^63, and every pass will divide it by 2. Meaning the loop only needs to run 63 times. The problem occurs when you have a huge jump, like the first prime factor is like 6,000,000,000+ or so. Ok. well you seem to know more than I gave you credit for then. I'm not sure if it is possible to prove if a(any) number that large is prime in 5 seconds. I just heard from wikipedia that: There is no known useful formula that yields all of the prime numbers and no composites. http://en.wikipedia.org/wiki/Prime_number http://en.wikipedia.org/wiki/Miller–Rabin_primality_testTry that test No. Good night. I'll do sieve when I feel like it in the future.
Good night, and good luck
|
Hey can someone tell me if my thought process is right? I'm thinking of how to find if a number is prime given fermats little thm. which states a^p is equivalent to a in mod p (I'm taking a class which covers basic public key exchange).
Knowing that to figure if some p is prime it's just a matter of figuring a^p, and for large p you can use the fast powering algorithm. That splits finding a^p as finding the product to a raised to the binary expansion of p. I.e. a^5 becomes a^(2^2) *a(2^0). Since this entire set of operations is done mod p, we never exceed p (for overflow - this is how pythons math.pow(x,y,z) works). So we end up with log2 multiplications to perform.
But on thinking about this, why how come you can't just use a=1 and then it would seem that every p is prime o.O...Anyone tell me what obvious part I'm doing wrong/missing?
|
On November 05 2012 16:45 teamamerica wrote: Hey can someone tell me if my thought process is right? I'm thinking of how to find if a number is prime given fermats little thm. which states a^p is equivalent to a in mod p (I'm taking a class which covers basic public key exchange).
Knowing that to figure if some p is prime it's just a matter of figuring a^p, and for large p you can use the fast powering algorithm. That splits finding a^p as finding the product to a raised to the binary expansion of p. I.e. a^5 becomes a^(2^2) *a(2^0). Since this entire set of operations is done mod p, we never exceed p (for overflow - this is how pythons math.pow(x,y,z) works). So we end up with log2 multiplications to perform.
But on thinking about this, why how come you can't just use a=1 and then it would seem that every p is prime o.O...Anyone tell me what obvious part I'm doing wrong/missing? Fermat's probable prime theorem is probable. You have to repeat the test for various moduli.
Even then, it's ridiculously fast to repeat ~100 times to get good confidence.
Note that Carmichael Numbers break Fermat's Little Theorem, but I believe the density of Carmichael numbers goes down for big numbers, so this can be ignored for applications like RSA.
|
On November 05 2012 17:25 mmp wrote:Show nested quote +On November 05 2012 16:45 teamamerica wrote: Hey can someone tell me if my thought process is right? I'm thinking of how to find if a number is prime given fermats little thm. which states a^p is equivalent to a in mod p (I'm taking a class which covers basic public key exchange).
Knowing that to figure if some p is prime it's just a matter of figuring a^p, and for large p you can use the fast powering algorithm. That splits finding a^p as finding the product to a raised to the binary expansion of p. I.e. a^5 becomes a^(2^2) *a(2^0). Since this entire set of operations is done mod p, we never exceed p (for overflow - this is how pythons math.pow(x,y,z) works). So we end up with log2 multiplications to perform.
But on thinking about this, why how come you can't just use a=1 and then it would seem that every p is prime o.O...Anyone tell me what obvious part I'm doing wrong/missing? Fermat's probable prime theorem is probable. You have to repeat the test for various moduli. Even then, it's ridiculously fast to repeat ~100 times to get good confidence. Note that Carmichael Numbers break Fermat's Little Theorem, but I believe the density of Carmichael numbers goes down for big numbers, so this can be ignored for applications like RSA.
Oh whoa, I never knew it was probable - also never knew about Carmicheal numbers (or that Fermats thm. failed at all TT). Well at least tomorrow when I ask my teacher some questions I'll look like I've actually been doing the reading!
Anyway, I saw some posts about learning C++ - I'm always an advocate for good books, esp. in languages where it's easy to do stuff the wrong way. So there's http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list
|
On November 04 2012 17:29 spinesheath wrote:Show nested quote +On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though.
I can tell you from 1st hand experience that you would miss your mobile phone functionality if C were to vanish now :D. C is here to stay and it will keep running the backend of a lot of stuff.
|
On November 04 2012 17:29 spinesheath wrote:Show nested quote +On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though. maybe in germany, in the US old codebases hardly ever use C
|
On November 06 2012 00:24 dakalro wrote:Show nested quote +On November 04 2012 17:29 spinesheath wrote:On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though. I can tell you from 1st hand experience that you would miss your mobile phone functionality if C were to vanish now :D. C is here to stay and it will keep running the backend of a lot of stuff. very true
|
On November 06 2012 01:56 nath wrote:Show nested quote +On November 04 2012 17:29 spinesheath wrote:On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though. maybe in germany, in the US old codebases hardly ever use C
As an american engineer who codes entirely in C, I disagree.
Also, I help build a corporate C compiler, ask me anything about those silly optimizations you want, though, under the hood its really just black magic.
|
On November 06 2012 00:24 dakalro wrote:Show nested quote +On November 04 2012 17:29 spinesheath wrote:On November 04 2012 07:25 Lysenko wrote:On November 04 2012 04:15 CecilSunkure wrote:On November 04 2012 02:09 Sawamura wrote: now if could write some C++ program practice ^_^ hehehe thanks for the practice anyway 5/5 I could do that. I'm thinking of some object oriented C first though. You know, virtualizing some C++ features in C. I was on my way to a much longer post, but I don't want to get in the way of what you're doing here with a lot of negativity, so I'll just ask. Who learns C today, absent a specific need to write embedded code, modify a UNIX or Linux kernel, or write a driver? I'm speaking as someone who paid several years of bills as a C programmer, working on both embedded applications and desktop applications. This was, however, 17 years ago, before (as far as I have personally seen, which is why I'm asking) the entire world moved on to C++. ** I mean, I can see doing it out of nostalgia, or because I got a cheap deal on some single-chip-computer development board, but that's about it. Is this a topic of interest for typical, highly-motivated CS students these days? I'm not saying it's bad, I just don't get it. You learn C to work with the crappy old codebase many companies still have. If you start a new project from scratch, you better have a damn good reason to use C. But if you work on something that uses old code, chances are it uses C. That's no reason to start with C as your first language though. I can tell you from 1st hand experience that you would miss your mobile phone functionality if C were to vanish now :D. C is here to stay and it will keep running the backend of a lot of stuff.
To all the folks who keep bringing up embedded applications in response to my comments about C largely not being used today (and the comments on my comments) please note that embedded applications are one of the specific examples (among others) I mentioned that would benefit from learning C.
|
United States10328 Posts
bros bros there exist polynomial-time primality tests like http://en.wikipedia.org/wiki/AKS_primality_test
factoring, on the other hand, is not known to be in P (which is why RSA hasn't been broken, yet)
(in fact a lot of cryptography relies on stuff which is not proven, such as: "factoring is hard"; "discrete log is hard"; and "there exists a pseudorandom number generator" [which is true if "discrete log is hard"])
On November 05 2012 17:25 mmp wrote: Fermat's probable prime theorem is probable. You have to repeat the test for various moduli.
hmm, I guess it's probabilistic if you choose random guys a and take a^n-1... but yeah the converse of Fermat's Little Theorem is not necessarily true.
|
Wiki says the original test had a worst case of Õ(log^12(n)) So that's like log(log(log(log...log(n)))))...))) 12 iterated logarithms. I had to go on wolfram to brush up on iterated logarithms. In that case checking for primes is pretty damn fast.
The Euler problem in question though was considered the third easiest question on the site. I highly doubt everyone who solved the problem knew AKS primality test considering the next few problems look really easy in comparison.
|
my solution to #5 used a simple bubble sort :D + Show Spoiler +#include <stdio.h> /* printf */
/* Swap the contents of two pointers. Do not modify the prototype. Use your function from PointerPractice_3 here. */ void SwapInts(int *a,int *b ) { /* Place your code here. Modify these lines. */ int temp = *a; *a = *b; *b = temp; }
/* Print contents of an array. Do not modify this function. */ void PrintArray( const int* array, const int size ) { int i; for(i = 0; i < size; ++i, ++array) { if(i != size - 1) printf( "%d, ", *array); else printf( "%d\n", *array); } }
int main( void ) { /* Create array on the stack. */ int stackArray[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
/* Get size of array. stackArray can be treated as pointer to first element. */ int arraySize = sizeof( stackArray ) / sizeof( *stackArray );
/* Can treat name of an array as pointer to first element. */ PrintArray( stackArray, arraySize );
/* Reverse the array here */ /**/ /**/ /**/ int i, j; for (i = (arraySize - 1); i > 0; i--) { for (j = 1; j <= i; j++) { if (stackArray[j-1] < stackArray[j]) { SwapInts(&stackArray[j-1], &stackArray[j]); } } }
PrintArray( stackArray, arraySize );
/* Correct output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 */
return 0; }
|
So, I know what it's finding... But I don't really know how it's finding it...
int arraySize = sizeof( stackArray ) / sizeof( *stackArray );
Can someone break down how exactly this is finding the arraySize for me please?
|
On December 20 2012 03:04 SeeDLiNg wrote: So, I know what it's finding... But I don't really know how it's finding it...
int arraySize = sizeof( stackArray ) / sizeof( *stackArray );
Can someone break down how exactly this is finding the arraySize for me please? Sure!
So with an array on the stack C actually knows the number of elements in the array. So when you do sizeof( stackArray ) the stackArray has not yet implicitly decayed into a pointer, and is actually being treated as a proper array. C multiplies the size of a single element in the array by the number of arrays, and this returns the number of bytes the entire array takes up within memory.
So then sizeof( *stackArray ) is implicitly decaying the stackArray identifier into a pointer and then dereferencing it. The value of *stackArray is that of the first element in the array, since an array's identifier can always be implicitly decayed into a pointer to the first element. So then the size of the first element is 4 bytes: the size of the integer first element.
Then you divide the size of bytes in total by the size in bytes of the first element to get the number of elements total.
|
|
|
|