View unanswered posts | View active topics It is currently Sun May 01, 2016 5:17 pm

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Re: Issue with the modulo operator with array
Author Message
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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 222 times
Sun Aug 25, 2013 3:31 pm
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
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
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
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
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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 226 times
Mon Aug 26, 2013 10:33 am
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
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
Rookie

Joined: Fri Sep 10, 2010 8:02 am
Posts: 6
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
Display posts from previous:  Sort by
 Page 1 of 1 [ 9 posts ]

#### Who is online

Users browsing this forum: No registered users and 1 guest

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

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge    2014 Robotics Academy Summer of Learning

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