Do you program and/or/nor script?

ta0kira · 12-05-2009, 01:08 PM

Quote:

Originally Posted by Wim Sturkenboom

I just code.

Shirley, you do other things as well.
Kevin Barry

GrapefruiTgirl · 12-05-2009, 01:15 PM

I make excellent french toast, with cinnamon, vanilla, and walnut/pecan bits in it. Mmmm

And, as much as I'd like to (and keep telling myself I will) learn C well enough to write something useful, I usually stick to bash these days; it's good brain exercise, and I really enjoy trying to make bash do everything.

Sasha

MBybee · 12-07-2009, 08:51 AM

Quote:

Originally Posted by GrapefruiTgirl

I make excellent french toast, with cinnamon, vanilla, and walnut/pecan bits in it. Mmmm

And, as much as I'd like to (and keep telling myself I will) learn C well enough to write something useful, I usually stick to bash these days; it's good brain exercise, and I really enjoy trying to make bash do everything.

Sasha

That sounds like an interesting challenge. Have you tried doing the prime numbers example with bash? I should think that would be fun

I usually use that as my first test in every new language (and on every system)

ta0kira · 12-07-2009, 01:43 PM

Quote:

Originally Posted by MBybee

That sounds like an interesting challenge. Have you tried doing the prime numbers example with bash? I should think that would be fun

I usually use that as my first test in every new language (and on every system)

Better yet, calculate an SVD! Good luck with that one.
Kevin Barry

GrapefruiTgirl · 12-07-2009, 02:48 PM

I don't know what an SVD is, and no, I haven't (bothered) to try calculating prime numbers using bash alone. But I *did* a couple years ago write a great PHP webpage for doing prime numbers. I started it because my roommate told me that way back when she was in some computer course many years ago, they were asked to come up with code to calculate prime numbers, and the code could be no longer than XX number of lines (I can't recall what XX was..) so I decided since I was doing web developing at that time and very much into PHP, I would see if I could do it.
I was quite impressed with the result, and it ran very fast on my local Apache installation. Unfortunately, about the same time my old 80Gib HDD died and shat its contents (including all my PHP codes) out in a million pieces, the free hosting provider I had been using got hacked and went down; when it resurfaced, all user data was gone. So, I no longer have that code :/

Note that this all happened before I learned about Linux, and regular backups

Sasha

MBybee · 12-07-2009, 03:43 PM

Quote:

Originally Posted by GrapefruiTgirl

I don't know what an SVD is, and no, I haven't (bothered) to try calculating prime numbers using bash alone. But I *did* a couple years ago write a great PHP webpage for doing prime numbers. I started it because my roommate told me that way back when she was in some computer course many years ago, they were asked to come up with code to calculate prime numbers, and the code could be no longer than XX number of lines (I can't recall what XX was..) so I decided since I was doing web developing at that time and very much into PHP, I would see if I could do it.
I was quite impressed with the result, and it ran very fast on my local Apache installation. Unfortunately, about the same time my old 80Gib HDD died and shat its contents (including all my PHP codes) out in a million pieces, the free hosting provider I had been using got hacked and went down; when it resurfaced, all user data was gone. So, I no longer have that code :/

Note that this all happened before I learned about Linux, and regular backups

Sasha

Ahh - I've given out that assignment a few times. I don't limit lines, however. I just award points for speed, clarity, and accuracy - usually sorting all primes under (some random limit).

I don't typically tell people *how* to do it, but nearly everyone uses the Sieve of Eratosthenes. It's probably the simplest method possible.

MTK358 · 12-07-2009, 04:02 PM

I read about the Sieve of Eratosthenes and it makes sense. I just wonder how can it be done without a list so big it takes up all your RAM?

PTrenholme · 12-07-2009, 04:33 PM

Quote:

Originally Posted by ta0kira

Better yet, calculate an SVD! Good luck with that one.
Kevin Barry

If by SVD you mean a singular value decomposition, that problem is fairly easily reduced to finding the eigenvalues of a symmetric, square matrix. That problem is fairly easily solved.

ta0kira · 12-07-2009, 04:35 PM

Quote:

Originally Posted by MTK358

I read about the Sieve of Eratosthenes and it makes sense. I just wonder how can it be done without a list so big it takes up all your RAM?

I've done it in the opposite manner, where rather than starting with a full list I created a list of primes as I went, which uses up less memory for huge ranges:

take the current number, mod out all integers (separately) in the list of primes aleady found <= its sqrt, skip to 3 if any are == 0
add the number to the list of primes
increment and return to 1

This could be done in bash fairly easily.
Kevin Barry

MTK358 · 12-07-2009, 04:39 PM

I'm not sure I understand. Maybe you can write it out more clearly?

ta0kira · 12-07-2009, 04:43 PM

Quote:

Originally Posted by PTrenholme

If by SVD you mean a singular value decomposition, that problem is fairly easily reduced to finding the eigenvalues of a symmetric, square matrix. That problem is fairly easily solved.

It's not a difficult problem, even to do by hand; however, it also requires finding eigenvectors, multiplying matrices, and possibly finding nullspaces. I'm not quite sure how you'd do that all in bash, unless you piped it to MATLAB or some other program. Granted, it would take a while to write something by hand in C/C++ without using a 3rd-party library, vs. forever in bash. The point is that multi-dimensional manipulation is somewhat difficult in bash.
Kevin Barry

MBybee · 12-07-2009, 04:46 PM

Quote:

Originally Posted by MTK358

I read about the Sieve of Eratosthenes and it makes sense. I just wonder how can it be done without a list so big it takes up all your RAM?

It's possible - I've done it on everything from VAX to IA64 and all sorts of platforms in between.
Give it a try

ta0kira · 12-07-2009, 04:53 PM

Quote:

Originally Posted by MTK358

I'm not sure I understand. Maybe you can write it out more clearly?

C++-ish pseudocode:

Code:

list primes
int current = 1
int maximum = 1000000

while ++current < maximum
{
  int root = sqrt(current)
  bool prime = true

  for I = 0; I < primes.size && primes[ I ] <= root; I++
    if current % primes[ I ] == 0
    {
      prime = false
      break
    }

  if prime
    primes.push_back(current)
}

Kevin Barry

ta0kira · 12-07-2009, 04:58 PM

Quote:

Originally Posted by MTK358

I read about the Sieve of Eratosthenes and it makes sense. I just wonder how can it be done without a list so big it takes up all your RAM?

Another way would be to do SoE with a moderately-sized array:

allocate an array of X integers, starting with where the previous iteration left off
remove all multiples of the primes already found
perform Sieve of Eratosthenes within the current array
push the remaining numbers (the primes) into a list of primes already found
return to 1

You can estimate the number of primes less than a number with x/ln(x); the percentage of primes drops quite a bit with magnitude.
Kevin Barry

MTK358 · 12-07-2009, 05:10 PM

Quote:

Originally Posted by ta0kira

C++-ish pseudocode:

Code:

list primes
int current = 1
int maximum = 1000000

while ++current < maximum
{
  int root = sqrt(current)
  bool prime = true

  for I = 0; I < primes.size && primes[ I ] <= root; I++
    if current % primes[ I ] == 0
    {
      prime = false
      break
    }

  if prime
    primes.push_back(current)
}

Kevin Barry

I still don't understand why this works, but I'll try it in Python.