Re: Old Stuff, Same Problems... (prime numbers)
At 11:39 AM 11/17/98 -0200, Cyberknight wrote: >I present here a program that checks if a number is or not >prime. It is the fastest code I could think of. Half of it is a >classical algorythm: divide X by 2; if no rest, it is not prime; >divide X by 3; if no rest, it is not prime... and so on until >X divided by X-1. I modified the algorythm in this way: if >the number is not a multiple of 2, then it can be, at most, >a multiple of 3, so one doesn't have to check till X-1, but >(X-1)/2, or in other words, the multiples of the number can >be at most (X-1)/2. In fact, you only have to check until SQR(X). Suppose X is not a prime. Then you can find two numbers A and B, where A * B = X and A <= B. If A > SQR(X) and B > SQR(X), then A * B > X. This is not the case, so A <= SQR(X) or B <= SQR(X). Because A <= B, it is certain that A <= SQR(X). This means that if X is not a prime, there is a number A <= SQR(X) which devides X. So, you only have to check until SQR(X). Modifications to the BASIC program: 25 DS=INT(SQR(DN)) 30 IFDD<=DSTHENIF(DNMODDD)=0THENP=0:GOTO40ELSEDD=DD+2:GOTO30 Line 25 is there because SQR is a slow function. If you put SQR(DN) in the IF statement, it is evaluated every loop, wasting a lot of time. Bye, Maarten MSX Mailinglist. To unsubscribe, send an email to [EMAIL PROTECTED] and put in the body (not subject) "unsubscribe msx [EMAIL PROTECTED]" (without the quotes :-) Problems? contact [EMAIL PROTECTED] (www.stack.nl/~wiebe/mailinglist/)
Re: Old Stuff, Same Problems...
Hi, [prime] >> 10 DEFINTA-Z:DD=3:P=1:INPUT"Number";DN: >>IFDN<2THENPRINTDN"is not a prime number (defined).":END >> 20 IFDN<>2THENIF(DNMOD2)=0THENP=0:DD=2:GOTO40 >> 30 IFDD<=(DN/DD)THENIF(DNMODDD)=0THENP=0:GOTO40ELSEDD=DD+2:GOTO30 >> 40 IFPTHENPRINTDN"is a prime number.":END >>ELSEPRINTDN"is NOT a prime number (multiple of"DD")." >If you want an even quicker algoritm, you don't need the division in the >loop, but you need a sqare root outside it [snip] There is another method which could be faster for really large numbers. The point is, that with the algorithm above, you still check a lot of possible divisors that don't need to be checked, namely all non-prime odd numbers. (9, 15, 19, 21 etc). The trick is to define an array P[SRQ(DN)], which is initially filled with "1"s. Now, do the next: 100 FOR I=1 TO SQR(DN) ' I know - SQR(DN) can be precalculated 110 IF P[I]=0 THEN 140 120 J = 2*I 130 IF J < SQR(DN) THEN P[J] = 0: J=J+I: GOTO 130 140 NEXT I Then, only those elements of P[] whose indexes are prime will still contain "1", the rest will be "0". Now, you only need to check these as possible divisors for DN. For small DN, the effort of creating the prime array is much higher than simply checking all odd numbers, that's why it can only work for large DN. Actually I'm not even sure if there _is_ a point beyond which this method is faster than the one mentioned first. Ah well, it's fun to see it anyway, ain't it :-) 150 FOR I=2 TO SQR(DN) 160 IF P[I] = 0 THEN 180 170 IF (DN MOD I) = 0 THEN PRINT DN "is not prime. multiple of " I: END 180 NEXT I 190 PRINT DN "is prime" Further optimizations left as excercise for the reader :-) By the way, he above method of calculating primes is known as the "sieve of Erathostenes". Eric (primes are an odd bunch o' numbers) MSX Mailinglist. To unsubscribe, send an email to [EMAIL PROTECTED] and put in the body (not subject) "unsubscribe msx [EMAIL PROTECTED]" (without the quotes :-) Problems? contact [EMAIL PROTECTED] (www.stack.nl/~wiebe/mailinglist/)
Re: Old Stuff, Same Problems...
Hi, Since I agree with the rest you wrote, I'll just quote this part: CLAUDIO MASSAO KAWATA - 900293 wrote: > A trivia about prime numbers: number 1 is not prime, as some > people think. If it was, no other number would be, because they > all would be multiples of at least one prime number (1 itself). > > I present here a program that checks if a number is or not > prime. It is the fastest code I could think of. Half of it is a > classical algorythm: divide X by 2; if no rest, it is not prime; > divide X by 3; if no rest, it is not prime... and so on until > X divided by X-1. I modified the algorythm in this way: if > the number is not a multiple of 2, then it can be, at most, > a multiple of 3, so one doesn't have to check till X-1, but > (X-1)/2, or in other words, the multiples of the number can > be at most (X-1)/2. Line 20 checks if number is 2 or multiple > of 2 (with that, you can step 2 by 2 instead of 1 by 1 of the > classic algorythm). In line 30, "IF DD<=(DN/DD) THEN..." is my > modification (the original should be "IF DD The program has to evaluate one extra division because of my > modification, but it saves a lot with the reduction of the search > range at each iteraction. Try it! Note: the program was originally > written in C. > > 10 DEFINTA-Z:DD=3:P=1:INPUT"Number";DN:IFDN<2THENPRINTDN"is not a prime number >(defined).":END > 20 IFDN<>2THENIF(DNMOD2)=0THENP=0:DD=2:GOTO40 > 30 IFDD<=(DN/DD)THENIF(DNMODDD)=0THENP=0:GOTO40ELSEDD=DD+2:GOTO30 > 40 IFPTHENPRINTDN"is a prime number.":ENDELSEPRINTDN"is NOT a prime number (multiple >of"DD")." > >... Cyberknight... > If you want an even quicker algoritm, you don't need the division in the loop, but you need a sqare root outside it (a bad approximation will do fine). The point is, that when your program ends the loop, dd=dn/dd, or in other words:dd^2=dn, or dd=sqr(dn). If you start with calculating sqr(dn), it will therefor be faster. If this is not an integer, use the first higher integer. That will be, I think, the fastest way to check if one specific number is prime. If, however, you want to calculate all prime numbers until a certain one, there is a faster method: try dividing by all prime numbers already found, until the number to check it with is higher than the square root of dn. I don't have a program ready to show what I mean, but I hope it is clear. Bye, shevek MSX Mailinglist. To unsubscribe, send an email to [EMAIL PROTECTED] and put in the body (not subject) "unsubscribe msx [EMAIL PROTECTED]" (without the quotes :-) Problems? contact [EMAIL PROTECTED] (www.stack.nl/~wiebe/mailinglist/)
Old Stuff, Same Problems...
Hi! |
A|A
(n n)
\_/
I've read some interesting old EMs, about copyrights,
"copywrongs", copy-protections, hacking and so one... A friend
of mine bought PC's "Frontier - Elite II" (hey, people all
around, except for the graphics, MSX version is far better!) It
had a protection of the kind "type in the first letter of word X
in line Y at page Z". Well, I played the game in his house and it
locked me twice because I either counted the letters wrong (it
was not clear in the manual if I had or not to consider the
manual's page titles) or the manual was wrong (it was a new
edition and I don't doubt it or the game could have been modified
without the corresponding updating on the other part). My friend
was also locked a few times and after loosing a dozen games, we'd
got a game cracker in the Net and sent the copy-protection to
hell. Summarizing, I don't think any kind of protection is worth
the stress upon any single customer.
"So, software makers cannot protect themselves from piracy?"
Of course they can. A message like "unregistered software"
("software registered to XYZ" is even better) is a good start,
because "registered" machines (those in offices and legal
organizations) cannot use unregistered software, and there are
the "real money", not in the domestic user. Videogames are a
special problem, because the "main stream" is the domestic user.
The best protection against piracy, I think, is a good price
AND a good game AND a good distribution: if the price is high,
it will be worth for the pirate to copy the software and the
manual; if the game is not good it won't seem worth to the user
to buy it; if the game is hard to find or to purchase, most
users will take the easiest way of piracy (for example, it was
absurdly hard to buy original Konami MSX software in Brazil,
because of high custom taxes and mailing costs). Small
softhouses cannot afford a big distribution plan. Small Famicom
and Super Famicom soft makers used to sell their products to
bigger enterprises, like Nintendo of America and Japan Enix.
Compile, from which we got so many wonders like Aleste and
Golvellius, was a small softhouse and could afford direct
distribution only in Japan and for "open systems", like MSX
and other Japanese machines. Super Famicom's "Super Aleste"
was released by Japan Toho (the original studio of Gojira
[Godzilla]). What I mean from all this is that it would be good
if home programmers and small softhouses could join to make
a really wide distribution net. There are surely good ideas
and programmers around. Buying large packs of diskettes and
printing many manuals at once would lower costs. A non-profit
organization would provide what's necessary to stop piracy.
Joining enough people to raise such project is difficult.
If the joy of having a program running in an extinct machine
ten years from now is not enough for someone, then move to
a "probably" long living plataform (I'm now programming in
JavaScript, which fortunately has almost nothing to do with
Java, it's more like HTML with IF-THEN-ELSE built-in). MSX has
a lot to give, still, and it's enough for me to have fun out of
it (that's why I only make freeware and public domain for MSX).
If it enjoys someone else, then it is an even better payment.
David Bradden, one of the programmers of "Elite", has released a
Famicom version, just for fun (it is a freeware and can be found
in the Net). Famicom don't have a block definition VRAM, so it
should be impossible to make vector graphics in it, but it has a
small RAM for block positioning and programmable video pointers.
He made the block positioning index point to ROM and the block
definition to the RAM, that is, something no one has thought
about before, and made the game. I wonder how many things about
MSX no one has thought about before. How many of them would be
worth purchasing as a game...?
Games also present another problem, easily noticable even in
this list: I HATE "3D Wolfenstein" and clones, some people love
them. I love shoot'em ups, while others simply prefer to die
than to play "Aleste". Though I don't like "battle modes", I
prefer them to the pretense real-time battles of "Dune II" and
similars, and others just cannot deal with pop-up combat menus
(they are easily beaten even by slimes). MSX users are very
ecletic in their likes and dislikes, from the classics of the
Colecovision convertions to the CRPGs of Microcabin. How to sell
a hundred copies of any program to such an audience? Maybe a
wonderfully programmed multi-style game, in which the player
could select the kind of "game style" it prefers... But it would
be too complex and expensive to be programmed. It would be a fun
to play "Episode II - Gopher no Yabou" ("Nemesis 3") in CRPG or
C-adventure style! It would be like pressing and making
"Majou Densetsu" ("Knightmare") become "The Maze of Galious" or
and play it as "Shalom" (Konami prefered to release them as
three independent games, of course). How to s
