View unanswered posts | View active topics It is currently Sat Dec 20, 2014 1:36 pm






Reply to topic  [ 9 posts ] 
Re: Issue with the modulo operator with array 
Author Message
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Issue with the modulo operator with array
I want to create a program that calculates the sum of all the even numbers of the Fibonacci sequence that are less than 4000000 and display the result on the NXT LCD screen. Before calculating the sum, I wrote the program to display each term satisfying each condition independently before applying the conjunction just for testing purpose.
Why is the last even number 10946 while the highest number less than 4000000 is 3524578. Please see attachment for the code and output.


Attachments:
fibonacci_seq.pdf [113.81 KiB]
Downloaded 169 times
Sun Aug 25, 2013 3:31 pm
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Issue with the modulo operator with array
I got a very large even number, not 10946. But I was doing it with virtual world. I'd bet it has something to do with doing a modulo on a floating point number. Modulo is generally done to integers.


Sun Aug 25, 2013 7:33 pm
Profile
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Issue with the modulo operator with array
Thanks for your reply. You may be right but it started displaying the numbers from 2 to 10946. If the float data type was an issue, i assume it would give a lot of unpredictable numbers. My question is why does it stop at 10946. As for the integer type, the memory allocation would not be enough to hold numbers up to 4000000. If you still have a new idea, please let me know. Thanks again.


Sun Aug 25, 2013 7:52 pm
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Issue with the modulo operator with array
There could be many explanations depending on how the compiler behaves. If the compiler does automatic type casting of the float type to integer type before doing modulo, then it should work. However, if it doesn't, the float data type's internal representation is IEEE 754 format with signed mantissa and signed exponent. I re-ran the program on an NXT with modified debug code to debug stream console:
Code:
task main()
{
    float fib[100];
    fib[0] = 1.0;
    fib[1] = 2.0;
    int i;
    for (i = 2; i < 100; i++)
    {
        fib[i] = fib[i - 2] + fib[i - 1];
    }
    wait1Msec(100);
    i = 0;
    while (i < 100)
    {
        writeDebugStream("[%3d] %0.0f(%x) -> %d", i, fib[i], fib[i], fib[i]%2);
        if (fib[i] % 2 == 0)
        {
            writeDebugStreamLine(" Even!");
        }
        else
        {
            writeDebugStreamLine("");
        }
        wait1Msec(100);
        i++;
    }
}

[  0] 1(1) -> 1
[  1] 2(2) -> 0 Even!
[  2] 3(3) -> 1
[  3] 5(5) -> 1
[  4] 8(8) -> 0 Even!
[  5] 13(d) -> 1
[  6] 21(15) -> 1
[  7] 34(22) -> 0 Even!
[  8] 55(37) -> 1
[  9] 89(59) -> 1
[ 10] 144(90) -> 0 Even!
[ 11] 233(e9) -> 1
[ 12] 377(179) -> 1
[ 13] 610(262) -> 0 Even!
[ 14] 987(3db) -> 1
[ 15] 1597(63d) -> 1
[ 16] 2584(a18) -> 0 Even!
[ 17] 4181(1055) -> 1
[ 18] 6765(1a6d) -> 1
[ 19] 10946(2ac2) -> 0 Even!
[ 20] 17711(452f) -> 1
[ 21] 28657(6ff1) -> 1
[ 22] 46368(b520) -> 1
[ 23] 75025(12511) -> 1
[ 24] 121393(1da31) -> 1
[ 25] 196418(2ff42) -> 1
[ 26] 317811(4d973) -> 1
[ 27] 514229(7d8b5) -> 1
[ 28] 832040(cb228) -> 1
[ 29] 1346269(148add) -> 1
[ 30] 2178309(213d05) -> 1
[ 31] 3524578(35c7e2) -> 1
[ 32] 5702887(5704e7) -> 1
[ 33] 9227465(8cccc9) -> 1
[ 34] 14930352(e3d1b0) -> 1
[ 35] 24157816(1709e78) -> 1
[ 36] 39088168(2547028) -> 1
[ 37] 63245984(3c50ea0) -> 1
[ 38] 102334152(6197ec8) -> 1
[ 39] 165580128(9de8d60) -> 1
[ 40] 267914272(ff80c20) -> 1
[ 41] 433494400(19d69980) -> 1
[ 42] 701408640(29cea580) -> 1
[ 43] 1134903040(43a53f00) -> 1
[ 44] 1836311680(6d73e480) -> 1
[ 45] 2971214848(7fffffff) -> 1
[ 46] 4807526400(7fffffff) -> 1
[ 47] 7778741248(7fffffff) -> 1
[ 48] 12586267648(7fffffff) -> 1
[ 49] 20365008896(7fffffff) -> 1
[ 50] 32951275520(7fffffff) -> 1
[ 51] 53316284416(7fffffff) -> 1
[ 52] 86267559936(7fffffff) -> 1
[ 53] 139583848448(7fffffff) -> 1
[ 54] 225851408384(7fffffff) -> 1
[ 55] 365435256832(7fffffff) -> 1
[ 56] 591286632448(7fffffff) -> 1
[ 57] 956721922048(7fffffff) -> 1
[ 58] 1548008554496(7fffffff) -> 1
[ 59] 2504730345472(7fffffff) -> 1
[ 60] 4052738899968(7fffffff) -> 1
[ 61] 6557469245440(7fffffff) -> 1
[ 62] 10610208145408(7fffffff) -> 1
[ 63] 17167677390848(7fffffff) -> 1
[ 64] 27777885536256(7fffffff) -> 1
[ 65] 44945561878528(7fffffff) -> 1
[ 66] 72723443220480(7fffffff) -> 1
[ 67] 117669000904704(7fffffff) -> 1
[ 68] 190392444125184(7fffffff) -> 1
[ 69] 308061428252672(7fffffff) -> 1
[ 70] 498453872377856(7fffffff) -> 1
[ 71] 806515267076096(7fffffff) -> 1
[ 72] 1304969173008384(7fffffff) -> 1
[ 73] 2111484440084480(7fffffff) -> 1
[ 74] 3416453747310592(7fffffff) -> 1
[ 75] 5527938053177344(7fffffff) -> 1
[ 76] 8944391800487936(7fffffff) -> 1
[ 77] 14472330390536193(7fffffff) -> 1
[ 78] 23416722191024128(7fffffff) -> 1
[ 79] 37889050434076674(7fffffff) -> 1
[ 80] 61305770477617152(7fffffff) -> 1
[ 81] 99194820911693815(7fffffff) -> 1
[ 82] 160500591389310975(7fffffff) -> 1
[ 83] 259695403711070195(7fffffff) -> 1
[ 84] 420195995100381151(7fffffff) -> 1
[ 85] 679891398811451346(7fffffff) -> 1
[ 86] 1100087359552094154(7fffffff) -> 1
[ 87] 1779978758363545686(7fffffff) -> 1
[ 88] 2880066255354593322(7fffffff) -> 1
[ 89] 4660044738840232044(7fffffff) -> 1
[ 90] 7540110994194824994(7fffffff) -> 1
[ 91] 12200155733035057783(7fffffff) -> 1
[ 92] 19740266727229882032(7fffffff) -> 1
[ 93] 31940421360753312707(7fffffff) -> 1
[ 94] 51680688087983191013(7fffffff) -> 1
[ 95] 83621113846783014014(7fffffff) -> 1
[ 96] 135301801934766210616(7fffffff) -> 1
[ 97] 218922915781549215317(7fffffff) -> 1
[ 98] 354224717716315463185(7fffffff) -> 1
[ 99] 573147651090050712228(7fffffff) -> 1

As you can see, at index 22, the even number 46368 has a binary representation of 0xb520. This is suspicious because this is at a point that it would be a negative value if it were a 16-bit integer. Again, the virtual world behaved differently (output below), it indicates they implement modulo differently. Virtual world seems more correct.
Code:
[  0] 1(1) -> 1
[  1] 2(2) -> 0 Even!
[  2] 3(3) -> 1
[  3] 5(5) -> 1
[  4] 8(8) -> 0 Even!
[  5] 13(d) -> 1
[  6] 21(15) -> 1
[  7] 34(22) -> 0 Even!
[  8] 55(37) -> 1
[  9] 89(59) -> 1
[ 10] 144(90) -> 0 Even!
[ 11] 233(e9) -> 1
[ 12] 377(179) -> 1
[ 13] 610(262) -> 0 Even!
[ 14] 987(3db) -> 1
[ 15] 1597(63d) -> 1
[ 16] 2584(a18) -> 0 Even!
[ 17] 4181(1055) -> 1
[ 18] 6765(1a6d) -> 1
[ 19] 10946(2ac2) -> 0 Even!
[ 20] 17711(452f) -> 1
[ 21] 28657(6ff1) -> 1
[ 22] 46368(b520) -> 0 Even!
[ 23] 75025(12511) -> 1
[ 24] 121393(1da31) -> -1
[ 25] 196418(2ff42) -> 0 Even!
[ 26] 317811(4d973) -> -1
[ 27] 514229(7d8b5) -> -1
[ 28] 832040(cb228) -> 0 Even!
[ 29] 1346269(148add) -> -1
[ 30] 2178309(213d05) -> 1
[ 31] 3524578(35c7e2) -> 0 Even!
[ 32] 5702887(5704e7) -> 1
[ 33] 9227465(8cccc9) -> -1
[ 34] 14930352(e3d1b0) -> 0 Even!
[ 35] 24157816(1709e78) -> 0 Even!
[ 36] 39088168(2547028) -> 0 Even!
[ 37] 63245984(3c50ea0) -> 0 Even!
[ 38] 102334152(6197ec8) -> 0 Even!
[ 39] 165580128(9de8d60) -> 0 Even!
[ 40] 267914272(ff80c20) -> 0 Even!
[ 41] 433494400(19d69980) -> 0 Even!
[ 42] 701408640(29cea580) -> 0 Even!
[ 43] 1134903040(43a53f00) -> 0 Even!
[ 44] 1836311680(6d73e480) -> 0 Even!
[ 45] 2971214848(80000000) -> 0 Even!
[ 46] 4807526400(80000000) -> 0 Even!
[ 47] 7778741248(80000000) -> 0 Even!
[ 48] 12586267648(80000000) -> 0 Even!
[ 49] 20365008896(80000000) -> 0 Even!
[ 50] 32951275520(80000000) -> 0 Even!
[ 51] 53316284416(80000000) -> 0 Even!
[ 52] 86267559936(80000000) -> 0 Even!
[ 53] 139583848448(80000000) -> 0 Even!
[ 54] 225851408384(80000000) -> 0 Even!
[ 55] 365435256832(80000000) -> 0 Even!
[ 56] 591286632448(80000000) -> 0 Even!
[ 57] 956721922048(80000000) -> 0 Even!
[ 58] 1548008554496(80000000) -> 0 Even!
[ 59] 2504730345472(80000000) -> 0 Even!
[ 60] 4052738899968(80000000) -> 0 Even!
[ 61] 6557469245440(80000000) -> 0 Even!
[ 62] 10610208145408(80000000) -> 0 Even!
[ 63] 17167677390848(80000000) -> 0 Even!
[ 64] 27777885536256(80000000) -> 0 Even!
[ 65] 44945561878528(80000000) -> 0 Even!
[ 66] 72723443220480(80000000) -> 0 Even!
[ 67] 117669000904704(80000000) -> 0 Even!
[ 68] 190392444125184(80000000) -> 0 Even!
[ 69] 308061428252672(80000000) -> 0 Even!
[ 70] 498453872377856(80000000) -> 0 Even!
[ 71] 806515267076096(80000000) -> 0 Even!
[ 72] 1304969173008384(80000000) -> 0 Even!
[ 73] 2111484440084480(80000000) -> 0 Even!
[ 74] 3416453747310592(80000000) -> 0 Even!
[ 75] 5527938053177344(80000000) -> 0 Even!
[ 76] 8944391800487936(80000000) -> 0 Even!
[ 77] 14472330390536192(80000000) -> 0 Even!
[ 78] 23416722191024128(80000000) -> 0 Even!
[ 79] 37889050434076672(80000000) -> 0 Even!
[ 80] 61305770477617152(80000000) -> 0 Even!
[ 81] 99194820911693824(80000000) -> 0 Even!
[ 82] 160500591389310980(80000000) -> 0 Even!
[ 83] 259695403711070210(80000000) -> 0 Even!
[ 84] 420195995100381180(80000000) -> 0 Even!
[ 85] 679891398811451390(80000000) -> 0 Even!
[ 86] 1100087359552094200(80000000) -> 0 Even!
[ 87] 1779978758363545600(80000000) -> 0 Even!
[ 88] 2880066255354593300(80000000) -> 0 Even!
[ 89] 4660044738840231900(80000000) -> 0 Even!
[ 90] 7540110994194825200(80000000) -> 0 Even!
[ 91] 12200155733035057000(80000000) -> 0 Even!
[ 92] 19740266727229882000(80000000) -> 0 Even!
[ 93] 31940421360753312000(80000000) -> 0 Even!
[ 94] 51680688087983194000(80000000) -> 0 Even!
[ 95] 83621113846783017000(80000000) -> 0 Even!
[ 96] 135301801934766210000(80000000) -> 0 Even!
[ 97] 218922915781549230000(80000000) -> 0 Even!
[ 98] 354224717716315440000(80000000) -> 0 Even!
[ 99] 573147651090050710000(80000000) -> 0 Even!


Mon Aug 26, 2013 1:34 am
Profile
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Re: Issue with the modulo operator with array
Thanks a lot for your time. Your reasoning makes a lot of sense. I am still trying to find other alternative to work around it while you all are trying to help me. Thanks again for your attention to my question and let me now if you find a better approach to the coding.


Mon Aug 26, 2013 8:13 am
Profile
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Issue with the modulo operator with array
Thank you all who were trying to help me with my question. After agreeing with Guru MHTS on the fact that the float data type could have been the problem since the modulo operation does not support it, I changed the type to long unsigned and I get the desired result. Thank a gain. in the original code, [color=#0000FF]if you want to try it, just change float fib[100] to long unsigned fib[100][/color]. Issue resolved


Mon Aug 26, 2013 8:36 am
Profile
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Issue with the modulo operator with array
Before sharing my solution to this problem, I would like to be thankful to Guru MHTS whose help has opened my eyes and led me to figure out a better to debug the program. the data type with the highest memory space in RobotC is long integer. When the output was displayed in the debugger window, I found out that at index 45, the value in fib[45] was negative and the reason being is because the sum of fib[43] and fib[44] was more than what a long integer can hold. This has led to unpredictable result when create an array with 100 elements. So, I decide to stop at 44 and create an array of 45 elements. See attached file for the code and the output


Attachments:
fibonacci_seq.pdf [173.54 KiB]
Downloaded 176 times
Mon Aug 26, 2013 10:33 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Issue with the modulo operator with array
Since Fibonacci sequence is positive integers only, you can use the unsigned long type. Although you said you would, your code used signed long. That's why you overflowed it to negative values. Also, if you just want to display the sum of all even Fibonacci numbers less than 4 million, a more efficient way to do it is like the following. Note that you no longer have to use an array to store any of the Fibonacci numbers, you just need N-2, N-1, N and the running sum. Then you don't have to determine how big the array should be.
Code:
task main()
{
    unsigned long fibNMinus2 = 1;
    unsigned long fibNMinus1 = 2;
    unsigned long fibN = fibNMinus2 + fibNMinus1;
    unsigned long sum = fibNMinus1;

    while (fibN < 4000000)
    {
        if (fibN%2 == 0)
        {
            sum += fibN;
        }

        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
        fibN = fibNMinus2 + fibNMinus1;
    }
    nxtDisplayCenteredTextLine(4, "%d", sum);
}


Mon Aug 26, 2013 1:33 pm
Profile
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
Post Re: Re: Issue with the modulo operator with array
Thanks again. I made a copy of your code for archive.


Mon Aug 26, 2013 3:08 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 9 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.