mIRC Home    About    Download    Register    News    Help

Print Thread
Page 1 of 2 1 2
Prime numbers #44607 28/08/03 04:05 PM
Joined: Aug 2003
Posts: 314
S
Sigh Offline OP
Fjord artisan
OP Offline
Fjord artisan
S
Joined: Aug 2003
Posts: 314
An isprime operator or $prime identifier would be good

Re: Prime numbers #44608 28/08/03 04:07 PM
Joined: Feb 2003
Posts: 2,803
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,803
What formula do you recommend it use?

It can take years to determine if a number is prime or not.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Prime numbers #44609 28/08/03 04:19 PM
Joined: Aug 2003
Posts: 314
S
Sigh Offline OP
Fjord artisan
OP Offline
Fjord artisan
S
Joined: Aug 2003
Posts: 314
There are many algorithms out there for such a calculation, none that I can recall the name of, but I was just making a suggestion. I didn't really consider the mechanics behind it. Sure it would take years to determine if a very large number was prime but what if there was some limitation to the identifier?

Re: Prime numbers #44610 28/08/03 08:56 PM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
It doesn't take years, it takes at most minutes, at least for the largest number mIRC supports. Plus, I must say if "isurl" was getting such high praise, I really don't see why mIRC shouldn't have an "isprime" it could be very useful. In the meantime, here is an algorithm that is pretty fast, any faster algorithms I know of would require so much coding (simulating vectors and such) that in mIRC scripting they would be slow.

Code:
alias isprime {
  if (2 // $1 || $int($1) != $1) { return $false }
  var %i = 3, %s = $sqrt($1)
  while (%i <= %s) {
    if (%i // $1) return $false
    inc %i 2
  }
  return $true
}


It's not nearly as fast as some other methods, but it works, and it works especially well for "common" numbers, for example to determine if 13115117933 is prime it took roughly 4 seconds, and that one requires a decent amount of work seeing as how, no it is no prime and the factor is 75289 which obviously required a decent amount of work to figure out. If you are trying to determine if a number that is less than 2^32-1 is prime, than that alias will work just fine.

But like I said, if an isurl operator is useful enough to be added to mIRC, then I'd say isprime is. Isprime could be coded much better if it were done in C++ code than in mIRC scripting because you could use more complex testing.

Re: Prime numbers #44611 28/08/03 09:12 PM
Joined: Aug 2003
Posts: 314
S
Sigh Offline OP
Fjord artisan
OP Offline
Fjord artisan
S
Joined: Aug 2003
Posts: 314
Yes, about the complexity of C++, that's why I suggested it. I came up with pretty much the same calculation (looping from 1 to $sqrt(N)) but if there is a method on C++, it would be useful to see included. Why the extra 2 // $1 though? That would be checked the first time the loop is run (if you began with %i equal to 2)

Re: Prime numbers #44612 28/08/03 09:14 PM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
Well, the reason is, if $1 is not divisible by 2, then it is not divisible by any multiple of 2, so instead of trying
2,3,4,5,6,7,8,... I set it up to do 2,3,5,7,9,... and if I started with %i = 2, the /inc %i 2 would make it 4, not 3, and then the next increment would make it 6 not 5. So I figured it is just easier to start at 3.

Re: Prime numbers #44613 28/08/03 09:28 PM
Joined: Dec 2002
Posts: 339
D
Doomstars Offline
Fjord artisan
Offline
Fjord artisan
D
Joined: Dec 2002
Posts: 339
I just use something like the below. By the way, there is a significant amount of people who consider one prime, so ignore that.

isprime {
var %t $ticks
if ($len($1) > 19) { return $ $+ error | halt }
if ($1 !isnum) { return $ $+ error | halt }
if ($1 < 1) { return $false | halt }
if ($1 != $int($1)) { return $false | halt }
if ($istok(1 2 3 5 7,$1,32)) { return $true | halt }
if (2 // $1) || (3 // $1) || (5 // $1) { return $false | halt }
var %n 1
var %a $sqrt($1)
while (%n < %a) {
inc %n 6
if (%n // $1) { return $false $calc($ticks - %t) | halt }
}
return $true $calc($ticks - %t)
}

Re: Prime numbers #44614 28/08/03 09:35 PM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
Just thought of a way to make that a bit faster.
Code:
alias isprime {
  if ($1 == 2) { return $true }
  if (2 // $1 || $int($1) != $1) { return $false }
  var %i = 3, %s = $sqrt($1)
  if ($int(%s) == %s) return $false
  while (%i &lt;= %s) {
    if (%i // $1) return $false %i
    inc %i 2
  }
  return $true
}


If the square root of a number is an integer, then the number can not be prime, because it can be divided by an integer, namely its square root, and get an integer answer. Additionally, stupid me, I forgot to include the special case of 2, which is prime.

See using C++, it could be done much faster. Division is a very costly operation, addition/subtraction are much faster. There is a very basic (I remember learning it in about 6th grade) algorithm that is called the Sieve of Eratosthenes. Unfortunately, that algorithm requires an array and since mIRC doesn't support arrays, even though it is a very simple algorithm, it is difficult to implement in an mIRC script.

Re: Prime numbers #44615 28/08/03 10:10 PM
Joined: Feb 2003
Posts: 2,803
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,803
What if you only try dividing against numbers that end in 1 or 3 or 7 or 9, only?
This should double the speed or better.

Code:
alias isprime {
  if ($1 == 2) { return $true }
  if (2 // $1 || $int($1) != $1) { return $false }
  var %s = $sqrt($1)
  if ($int(%s) == %s) return $false
  var %i = 0, %s = $int($calc(%s / 10))
  while (%i &lt;= %s) {
    if (%i $+ 1 // $1) return $false
    if (%i $+ 3 // $1) return $false
    if (%i $+ 7 // $1) return $false
    if (%i $+ 9 // $1) return $false
    inc %i
  }
  return $true
}

I'm not sure if this would miss anything at the start or end, but should be accurate for the bulk of the loop. Extra coding is probably necessary.

I just used your existing code, I would personally write it slightly differently. I would also check if (*1 iswm $1) || (*3 iswm $1) || (*7 iswm $1) || (*9 iswm $1) or just add to your check if (2 // $1 || $int($1) != $1 || *5 iswm $1) { return $false }.

- Raccoon

Heh Doomstars, I just noticed that myself.

Last edited by Raccoon; 28/08/03 10:23 PM.

Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Prime numbers #44616 28/08/03 10:19 PM
Joined: Dec 2002
Posts: 339
D
Doomstars Offline
Fjord artisan
Offline
Fjord artisan
D
Joined: Dec 2002
Posts: 339
That's basically what I posted. Except 5's are hit now and then.

Re: Prime numbers #44617 29/08/03 12:18 AM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
Well your snippet there misses a ton of prime numbers. Just doing a little test of primes from 1 ... 100 your algorithm missed:
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

All of those are prime but your algorithm says they are not.

Doomstars is also broken. His works fine for 1 ... 100, but if I do 1 ... 500, then his identifies 121 187 253 289 319 341 391 407 451 473 493 as prime numbers, however, none of those are actually prime. The obvious one would be 121 which is 11*11.

You both had interesting ideas, but they just don't work.

Re: Prime numbers #44618 29/08/03 12:48 AM
Joined: Feb 2003
Posts: 2,803
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,803
I think my method is accurate, but there's an error in my syntex somewhere. That's every prime number between 3-100, so it's clearly hanging up on something.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Prime numbers #44619 29/08/03 12:57 AM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
Indeed, I see the problem,
if ($1 // %i $+ 1) return $false
if ($1 // %i $+ 3) return $false
if ($1 // %i $+ 7) return $false
if ($1 // %i $+ 9) return $false
You had those backwards. (%i $+ 1 // $1)
// is "v2 is a multiple of v1" so you need to reverse it. However, even after doing that it still misses a bunch.

These are reported as not-prime (composite):
3 7
And these are reported as prime:
35 39 45 5155 57 63 65 69 75 77 85 87 91 93 95 99

Re: Prime numbers #44620 29/08/03 01:03 AM
Joined: Feb 2003
Posts: 2,803
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,803
ay, an initial check against 3, 5, 7 and 11 should be made it seems.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Prime numbers #44621 29/08/03 07:09 AM
Joined: Dec 2002
Posts: 339
D
Doomstars Offline
Fjord artisan
Offline
Fjord artisan
D
Joined: Dec 2002
Posts: 339
I think the below is correct, but I could be wrong again. But down to an issue. I think $isprime would be a good identifier, but how many else would use it? Hopefully $isprime(number,0) would count 1 as not a prime. And $isprime(number,1) would count 1 as a prime. There are some who consider one as a prime. Why they do, it's because of the theory the numbers 1, 2, and 3 compose all of reality.
isprime {
var %t $ticks
if ($len($1) > 19) { return $ $+ error | halt }
if ($1 !isnum) { return $ $+ error | halt }
if ($1 < 1) { return $false | halt }
if ($1 != $int($1)) { return $false | halt }
if ($istok(1 2 3,$1,32)) { return $true | halt }
if (2 // $1) { return $false | halt }
var %n 1
var %a $sqrt($1)
while (%n < %a) {
inc %n 2
if (%n // $1) { return $false $calc($ticks - %t) | halt }
}
return $true $calc($ticks - %t)
}

Re: Prime numbers #44622 29/08/03 08:27 PM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
Quote:
Hopefully $isprime(number,0) would count 1 as not a prime. And $isprime(number,1) would count 1 as a prime. There are some who consider one as a prime. Why they do, it's because of the theory the numbers 1, 2, and 3 compose all of reality.

I hope it doesn't. Yes some peope say that, and some people say that 0 is both even and odd. But guess what? Those people are wrong. Thats like saying "well some people go around saying 2+2 is 5, so there should be a $calc(2+2,1) that makes it say 5." Just because people say it doesn't make it true; 1 is NOT prime. mIRC should not include an identifier that will give a wrong answer, and saying 1 is prime is wrong.

Re: Prime numbers #44623 30/08/03 12:41 AM
Joined: Dec 2002
Posts: 339
D
Doomstars Offline
Fjord artisan
Offline
Fjord artisan
D
Joined: Dec 2002
Posts: 339
I'm not wrong. And I'm not going to argue.

Re: Prime numbers #44624 30/08/03 12:43 AM
Joined: Dec 2002
Posts: 2,809
C
codemastr Offline
Hoopy frood
Offline
Hoopy frood
C
Joined: Dec 2002
Posts: 2,809
I didn't say you were wrong, I know there are people who say 1 is prime, I'm saying THOSE people are wrong.

Re: Prime numbers #44625 30/08/03 01:05 AM
Joined: Dec 2002
Posts: 339
D
Doomstars Offline
Fjord artisan
Offline
Fjord artisan
D
Joined: Dec 2002
Posts: 339
And I agree one can be considered prime. Which is one method. I'm not going to get into this discussion, it will just be a huge arguement.

Re: Prime numbers #44626 30/08/03 09:08 AM
Joined: Feb 2003
Posts: 2,803
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,803
One is neither prime NOR not prime.

$isprime(1) should raise an error, just as $calc(1 / 0) causes a Divide By Zero.
* $isprime(): Isprimed By One.

One might say that 1 / 0 == Zero, while others say it == One.

Neither are right, neither are wrong.

- Raccoon


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Page 1 of 2 1 2