Algorithms

Paul Conrad11-Aug-07 10:28

11-Aug-07 10:28

There does seem to be an unfortunate rash of laziness around some of these forums lately Sigh | :sigh:

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

Stephen Hewitt29-Jul-07 15:41

Stephen Hewitt

29-Jul-07 15:41

You could consider using regular expressions.

Steve

Paul Conrad29-Jul-07 17:36

29-Jul-07 17:36

Yep. Not sure what kind of regular expression he could use, but maybe Expresso[^] could be useful Smile | :)

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

Luc Pattyn29-Jul-07 23:56

Luc Pattyn

29-Jul-07 23:56

Hi,

this could be very easy, depends on your definition of pattern.

if your example 236321236 contains two patterns for you, that is 23 (twice),
then the following will do. If the fact that 236 appears twice is a pattern too,
then it is harder.

Here is my algorithm in pseudo-code (i.e. approx C#); some details may
be incorrect, but you will get the general idea; it is quadratic which
is good enough for phone numbers I guess.

string s="my text to analyze";
int sLength=s.Length;
for (int i=0; i<sLength-1; i++) {
    char c1=s[i];
    char c2=s[i+1];
    int diff=c2-c1;
    if (diff==0) log("double char");
    if (diff*diff==1) log("two char series");
    for (int len=3; len<sLength-i; len++) {  // for 3d, 4th, ... char in candidate
        c2+=diff;
        char c=s[i+len-1];
        if (c2==c) log("series extends to "+len+" chars");
        else break;
    }
}

As you can see, nothing fancy, no tricks, no regex...
Smile | :)

Luc Pattyn

try { [Search CP Articles] [Search CP Forums] [Forum Guidelines] [My Articles] }
catch { [Google] }

Primality Test

shiraztk27-Jul-07 7:47

27-Jul-07 7:47

Hi
I am not sure if this is true or not, but my initial tests gave a positive result

To check for primality of P

if 4 does not perfectly divide the perimeter of all the rectangles with area (P-1) then P is prime.

Regards

The Best Religion is Science.
Once you understand it, you will know God.

Paul Conrad27-Jul-07 8:17

27-Jul-07 8:17

Do you have a link to this, so it can be investigated/verified?

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

cp987627-Jul-07 11:40

cp9876

27-Jul-07 11:40

Not true, fails for 15, 27, 35, ..

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Paul Conrad27-Jul-07 19:50

27-Jul-07 19:50

cp9876 wrote:
Not true, fails for 15, 27, 35

Observant and quick, I must say Smile | :)

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

shiraztk30-Jul-07 7:31

30-Jul-07 7:31

Hi
| Not true, fails for 15, 27, 35

ture... Smile | :)

i was trying with big numbers and found this working...didnt notice that it failed for small numbers, infact it fails for large numbers also.

Regards

The Best Religion is Science.
Once you understand it, you will know God.

Paul Conrad30-Jul-07 10:52

30-Jul-07 10:52

You ought to direct your reply to cp9876...

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

cp987630-Jul-07 23:53

cp9876

30-Jul-07 23:53

It is pretty easy to see that it identifies any number of the form 4k+3 as prime.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Gyan Prakash8-Aug-07 22:00

Gyan Prakash

8-Aug-07 22:00

Hey Gui you are giving some what like silly idea. Don't you know 15,27, 35 are not prime.

gyan

Gyan Prakash8-Aug-07 21:55

Gyan Prakash

8-Aug-07 21:55

This idea is not clear cut for all primes. For example 13 is a prime number but 13-1=12 is divisible by 4. I mean that what happens if 4 perfectly divides p-1???

Gyan

Magics of 4

shiraztk26-Jul-07 8:49

26-Jul-07 8:49

Hi
Just found some wonderful properties of number 4.

1. 4 is the only perfect square whose reciprocal is also a perfect square.

2. Any perfect square when devided by 4 gives a reminder of either 1 or 0.

Is this something already known?

The Best Religion is Science.
Once you understand it, you will know God.

Maximilien26-Jul-07 9:27

Maximilien

26-Jul-07 9:27

Zainu wrote:
Is this something already known?

probably for a few hundred years.

Maximilien Lincourt
Your Head A Splode - Strong Bad

David Crow26-Jul-07 10:50

David Crow

26-Jul-07 10:50

Zainu wrote:
Is this something already known?

Technically, yes, I'm fairly sure that it is known by at least one person. I'm sure others will claim knowledge of it, too. Whether they do or not, you'll never know for sure.

"A good athlete is the result of a good and worthy opponent." - David Crow

"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne

CPallini26-Jul-07 12:18

CPallini

26-Jul-07 12:18

Zainu wrote:
4 is the only perfect square whose reciprocal is also a perfect square.

hence 1/4 is a perfect square while, for instance, 1/9 not?
Smile | :)

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.

cp987626-Jul-07 13:32

cp9876

26-Jul-07 13:32

Sounds like you are just discovering the magic of Number Theory, you can find lots of interesting resources on the web.

I'm not sure what you are implying with (1), but (2) is very well known. 0 and 1 are called the quadratic residues mod 4. Some other examples, the same thing is true mod 3, but in mod 8 the residues are 0,1,4.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

shiraztk27-Jul-07 4:00

27-Jul-07 4:00

Hi all

Yes, you can find a whole lot here

http://mathworld.wolfram.com/QuadraticResidue.html

Regards

The Best Religion is Science.
Once you understand it, you will know God.

Paul Conrad27-Jul-07 19:50

27-Jul-07 19:50

Mathworld is a great website, alot of good stuff there Smile | :)

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

Linear line

flippydeflippydebop25-Jul-07 9:15

flippydeflippydebop

25-Jul-07 9:15

Hiya guys.. Using C++ does anyone know how i can tell if a line is linear or not? I want the user to enter 5 readings which i can plot on a chart. However i would like a function to find out if the plotted line is linear.

Any help would be greatly appreciated!

Dan Neely25-Jul-07 9:35

Dan Neely

25-Jul-07 9:35

EDIT: Not sure if this is needed or not: if the slope between x_1,y_1 and x_5,y_5 is greater than 1, swap the x and y values for each coordinate pair. This swap is needed to keep the delta value in the next step smaller than 1.

Create a function for the line y = f(x) using points 1 and 5. Then of each of the 3 points in the middle calculate f(x_n), if ABS(f(x_n) - y_n) < 1, then x_n,y_n is on on the line (give or take the rounding error from forcing integral values).

--
You have to explain to them [VB coders] what you mean by "typed". their first response is likely to be something like, "Of course my code is typed. Do you think i magically project it onto the screen with the power of my mind?" --- John Simmons / outlaw programmer

Luc Pattyn25-Jul-07 11:14

Luc Pattyn

25-Jul-07 11:14

Hi Dan,

Same idea, but without any math showing, the lazy approach:

- Create a GraphicsPath
- add the line connecting the end points
- widen with a pen (I guess width=3, more gives more tolerance)
- check all points fall within (that's GraphicsPath.IsVisible)

Smile | :)

Luc Pattyn

try { [Search CP Articles] [Search CP Forums] [Forum Guidelines] [My Articles] }
catch { [Google] }

flippydeflippydebop25-Jul-07 20:30

flippydeflippydebop

25-Jul-07 20:30

Hiya Luc. Thanks also for your reply. This is an interesting approach here, however GraphicsPath is a .net class while i am using native C++/MFC.