Method for comparing two arrays

[Claryn]

Hi.

 

I am working on a simple program that takes one array and checks it's contents with another array.

 

I have the array series, that contains approx. 140000 sorted numbers, varying from 0 - 415000. 

I have the array fib, that contains 30 sorted numbers, varying from 0 - 415000.

 

What I want to do, is make a method that compares series to fib, and writes down how many numbers there are between the common numbers in the two arrays.

 

I wrote this, but it doesn't seem to work, and I have been staring at it for too long to really see the error.

    public static void checkFibonacci(int fib [], int series [])    {    	int count = 0;    	int poscount = 0;    	int [] position = new int [32];    	for (int n = 0; n < series.length; n++)    	{    		for (int i = 0; i < fib.length; i++)     		{    			if ( series[n] == fib[i]  )     			{    				position[poscount] = count;    				poscount++;    			}    				    			count++;    		}    	}    	    	for (int j = 0; j < position.length; j++)    	{    		System.out.println(position[j]);    	}    }

Method: http://pastebin.com/T24vc6Kz

 

[Philosobyte]

What is the purpose of the variable "count"? It seems to me as if it's supposed to be analogous to "i", but you're not resetting it to zero every time the internal for loop starts. 

[Claryn]

What is the purpose of the variable "count"? It seems to me as if it's supposed to be analogous to "i", but you're not resetting it to zero every time the internal for loop starts. 

 

The purpose is to keep track of how many numbers in series that is has checked, and then save the number into the new array that says how many numbers that are between the common numbers. 

[Philosobyte]

The purpose is to keep track of how many numbers in series that is has checked, and then save the number into the new array that says how many numbers that are between the common numbers. 

I assume you mean count equals the number of numbers in between fibonacci numbers in the series[]. Then you would have to reset count to 0 in the if statement and use count++ in the outer for loop. 

 

I have to go offline for 40 minutes, reply to you later. 

[Claryn]

I got a very different result by doing that, but it still doesn't make sense.

 

Here are the first couple of numbers in the series array:

0   5   10   13   17   20   25   26   29   34   37   40   41   45   50   52   53   58   61   65   65   68   73   74   80   82   85   85   89   90   97   100   101   104   106   109   113   116   117   122   125   125   130   130   136   137   145   145   146   148   149   153   157   160   164   169   170   170   173   178   180   181   185   185   193   194   197   200   202   205   205   208   212   218   221   221   225   226   229   232   233

And the fib array consists for the 30 first fibonacci-numbers.

 

So since 5 exists in series and fib, it should save the number 1 in the position array.

It should then count 1, until it hits 13 which is a fibonacci-number. Then it should count 6, until it hits 34, yet another fibonacci-number. Then 18 more until 89, which is the next fibonacci-number.

 

The output should then start with: 1 1 6 18...

 

However, the position array outputs: 

0 31 6 66 194 610 1666 1697 32...

 

That is when I reset count in the if-statement. When I do not reset it, this is the output:

0 31 37 103 297 907 2573 4270 4302...

 

Here is the whole program, if you'd like to look at the rest:

(Yes, I know this is a very tedious algorithm, but I just need to find the answer, and not have it be very efficient.)

http://pastebin.com/eb1UCA7d

 

For those wondering;

 

I am trying to investigate a relationship between Pythagorean Triples and Fibonacci numbers. The series array contains the first 412000 hypotenuses that are part of a pythagorean triple. 

[Philosobyte]

edit: never mind for now

[PrimeSonic]

So if I understand correctly, you want to feed an algorithm with two arrays with sorted numbers and see how many numbers it has in common.

 

With those assumptions, you could just as well also store those numbers as well. But let me see if I can offer you a different approach.

public static int[] CheckOrderedSequences(int[] seriesA, int[] seriesB){    int posA = 0;    int posB = 0;    int posR = 0;    int lengthA = seriesA.Length();    int lengthB = seriesB.Length();    int resultSize = Math.Min(lengthA, lengthB);    int resultSeries = new int[resultSize];    while (posA < lengthA && posB < lengthB)    {        if (seriesA[posA] == seriesB[posB])        {            resultSeries[posR] = seriesA[posA];            posR++;            posA++;            posB++;        }        else if (seriesA[posA] < seriesB[posB])        {            posA++;        }        else //if (seriesA[posA] > seriesB[posB])        {           posB++;        }    }    return resultSeries;    }

I just threw this together but here's the approach.

 

1) Assume arrays are ordered. Doesn't matter if they are different sizes.

2) Comparison is done by advancing on each array as needed.

2a) If the values match, add the match to the result and advance on both arrays.

2b) If the values don't match, advance the array with the lesser of the two values and compare again.

2c) As soon as you've reached the end of an array, you've checked all you can check and can safely return the results found.

 

Please do refine this if you find it useful. This approach should give you the numbers in common in the ordered arrays and should return its results in fewer comparisons than the approach you started with.

[Philosobyte]

snip

The Fibonacci numbers start with 0, 1, 1, 2, 3, 5. 

 

If you want the number of numbers in between Fibonacci numbers, then the position array would look like this:

 

Since the first number in the series, 0, is a Fibonacci number, the first number in the position array should be 0. 

Then the second number in the position array should be 0 again, because 5 is a fibonacci number.

Then the third number in the position array should be 1 because there is one number between 5 and 13. 

Then the fourth number in the position array should be 5 because there are five numbers between 13 and 34.

 

So, 0, 0, 1, 5. 

 

If you want the number of numbers checked to get a Fibonacci number, then everything would be incremented by one, so

1, 1, 2, 6. 

 

Am I misunderstanding something?

 

This is a version which uses labels. It works for the 0, 0, 1, 5 method. If you want the 1, 1, 2, 6 method, just move the count++ to the beginning of the loop.

public static void checkFibonacci(int fib [], int series []){    int count = 0;    int poscount = 0;    int [] position = new int [32];    Outer:    for (int n = 0; n < series.length; n++)    {        Inner:        for (int i = 0; i < fib.length; i++)        {            if ( series[n] == fib[i] )            {                position[poscount] = count;                poscount++;                count = 0;                continue Outer;            }        }        count++;    }    for (int j = 0; j < position.length; j++)    {        System.out.println(position[j]);    }}

I'm not sure if you learned using loop breaks yet, so I included a simple version using a boolean. If you need any clarification on why I did something, ask.

public static void checkFibonacci(int fib [], int series []){    int count = 0;    int poscount = 0;    boolean matched = false;    int [] position = new int [32];    for (int n = 0; n < series.length; n++)    {        matched = false;        for (int i = 0; i < fib.length; i++)        {            if ( series[n] == fib[i] && !matched )            {                position[poscount] = count;                poscount++;                count = 0;                matched = true;            }        }        if(!matched) {            count++;        }    }    for (int j = 0; j < position.length; j++)    {        System.out.println(position[j]);    }}

Edited September 16, 2015 by Raymondbl

[Philosobyte]

snip

He's not looking for the numbers in common. He's looking for the distance between occurrences of Fibonacci numbers in the series array.

[PrimeSonic]

He's not looking for the numbers in common. He's looking for the distance between occurrences of Fibonacci numbers in the series array.

Okay. So I didn't get that reading the first time through. Thanks for clarifying.

 

So if you wanted the distances between occurrences/matches, add a counter for the distance you want count.

 

public static int[] CheckOrderedSequences(int[] seriesA, int[] seriesB){    int posA = 0;    int posB = 0;    int posR = 0;    int lengthA = seriesA.Length();    int lengthB = seriesB.Length();    int distancesSize = Math.Min(lengthA, lengthB);    int distanceSeries = new int[resultSize];    int dCount = 0;    while (posA < lengthA && posB < lengthB)    {        if (seriesA[posA] == seriesB[posB])        {            distanceSeries[posR] = dCount;            posR++;            posA++;            posB++;            dCount = 0;        }        else if (seriesA[posA] < seriesB[posB])        {            posA++;            dCount++;        }        else //if (seriesA[posA] > seriesB[posB])        {           posB++;        }    }    return resultSeries;    }

Same basic way of traversing the arrays, but it stores the count you're looking for. Again, modify this to best suite your needs.

I tackled this with a more generic approach, without necessarily thinking about fibonacci or anything. Just ordered number sequences.

[Claryn]

 

snip

 

Thanks.  This solved the problem.

Now I just need to look at my generation of pythagorean triples, since only every second fibonacci-number is supposed to be in the series array, but that is another problem that needs modifications to my mathematical model

 

Thanks a lot for the help!

[Philosobyte]

Thanks.  This solved the problem.

Now I just need to look at my generation of pythagorean triples, since only every second fibonacci-number is supposed to be in the series array, but that is another problem that needs modifications to my mathematical model

 

Thanks a lot for the help!

No problem. But do you actually understand the code? 

I'd be happy to explain anything you don't understand. 

 

You should thank @PrimeSonic too for his efforts, even if you don't want to use his code, which is pretty clean, by the way. 

[Claryn]

No problem. But do you actually understand the code? 

I'd be happy to explain anything you don't understand. 

 

You should thank @PrimeSonic too for his efforts, even if you don't want to use his code, which is pretty clean, by the way. 

Yes, I understood your code. 

Here is what wolfram-alpha thinks of the result.. I am a bit clueless.. eh.

 

And yes thanks to @PrimeSonic too, although I didn't quite understand the code, I am grateful for your effort. 

[PrimeSonic]

Yeah, sometimes certain algorithms are best understood visually.

Sadly, with only text I feel something is lost in translation.

 

Glad you got what you needed and hopefully you'll take away even more from this experience than you expected.