30 berichten aan het bekijken - 1 tot 30 (van in totaal 44)
  • Q:
    Bijdrager
    vikking

    C: grote getallen optellen word een negatief getal.

    Ik heb een programma dat de Fibonacci reeks genereert:
    [code:1:81c028dc3d]#include <stdio.h>

    int main(void){
    // declarations
    int a, b, c;
    int count, i;
    a = 0;
    b = 1;

    printf("How many Fibonacci numbers?t");
    scanf("%d", &count);

    // here we go
    count = count-2;
    printf("1 ");
    for(i = 0; i <= count; i++){
    c = a + b;
    printf("%d ", c);
    a = b;
    b = c;
    }
    printf("n");
    return 0;
    }[/code:1:81c028dc3d]
    Maar als ik bv 50 van die getallen vraag gebeurt er dit:

    1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 -1323752223 512559680 -811192543 -298632863

    Volgens mij is 1134903170 + 1836311903 nog steeds niet gelijk aan -1323752223… Dit gebeurt zelfs wanneer ik a, b en c declare als een unsigned int… Hoe los ik dit op?

    Bijdrager
    njdewit

    Die %d interpreteert ‘c’ per definitie als een signed integer. Maak er eens %u van voor de grap.

    Bijdrager
    vikking
    ”njdewit”

    Die %d interpreteert ‘c’ per definitie als een signed integer. Maak er eens %u van voor de grap.

    Hehe, bedankt, maar bij grote getallen klopt het ook niet meer… Is dit omdat ik dan aan de grens van int zit? Hoe zorg ik ervoor dat ik in ‘a’ een groter getal kan opslaan?

    Bijdrager
    njdewit

    Klopt, de standaard integer op het platform dat jij gebruikt is er een van 32-bits. Dit houdt in dat je 2 (bit kan aan of uit) tot de macht 32 combinaties kunt vormen en in de unsigned vorm dus een dergelijk aantal cijfers uit kunt drukken.

    Om negatieve getallen aan te duiden naast positieve (voor de standaard c.q signed integer dus) wordt er een trucje toegepast dat two’s complement heet, lees daar ook maar eens wat over: http://en.wikipedia.org/wiki/Two’s_complement

    Dat zou het e.e.a moeten verhelderen.

    Bijdrager
    iJoost

    Gebruik een long.

    Bijdrager
    njdewit

    What the hell is that going to change? Toegegeven, het had leuk geweest als een long op 32-bit compilers keurig 64-bit zou zijn opgebroken in een low and high (d)word maar de realiteit is dat ze gewoon 32-bit zijn.

    (of doet apple’s gcc dat stiekem anders? danwel zie ik iets stoms over het hoofd)

    Bijdrager
    vikking

    Hmmzz, als ik hem 5000 getallen laat printen word op een bepaald moment zelfs kleiner! Bv dit:

    4109296160
    3359777681
    3174106545
    2238916930
    1118056179

    kan toch niet echt he?

    Bijdrager
    Buzz

    Daarom moet je in belangrijke programma’s ook altijd controles op integer overflows inbouwen, als dat niet al door je programmeertaal/compiler geregeld wordt.

    Bijdrager
    njdewit

    Neem nou maar aan dat wat daar staat gewoon klopt:) Zowel je a, b als c gaan vrolijk wrappen (na het hoogst mogelijke getal, te weten ((2^32)-1) komt gewoon weer 0 namelijk) dus het maakt allemaal niet ontzettend veel sense meer wat je dan uit loopt te rekenen.

    Bijdrager
    vikking
    ”njdewit”

    na het hoogst mogelijke getal, te weten ((2^32)-1) komt gewoon weer 0 namelijk.

    Beuh? Als ik een long heb waarin ik zet “(pow(2, 32))-1” (heb math.h geinclude) krijg ik het getal 2147483647, terwijl als ik het met iets anders bereken dit krijg: 4294967295…

    Bijdrager
    njdewit

    Sorry, ik bedoel dat dat er *na* komt.

    Neem het volgende:

    unsigned int a1 = 0xffffffff; // ofwel max_int ofwel wat zonder overflow pow(2,32)-1 zou zijn
    unsigned int a2 = a1 + 1;
    printf(“%u %un”, a1, a2);

    dan krijg je resp. MAX_INT (alle bits aan, max. getal) en 0, a2 is wrapped (alle bits uit)
    vervang je die unsigned int’s voor longs, krijg je hetzelfde, iig op de 32-bit compilers die ik tot nu toe gebruikt heb die een long gewoon als een 32-bit getal zien

    print je de getallen uit dmv %d (signed interpretatie) krijg je -1 en 0, a2 gezien alle bits op 0 (wrapped) gewoon wederom de representatie van 0 is, en -1 gezien alle bits aan daar de representatie van is (zie two’s complement verhaal waar ik een wikipedia linkje naar heb gepost eerder)

    Bijdrager
    Buzz

    Het tweede antwoord is natuurlijk juist. Bij het eerste antwoord heb je blijkbaar last van een integer overflow en is je antwoord dus niet juist. Je loopt hier dus tegen de beperkingen van je CPU aan. Er zijn natuurlijk trucs om die te omzeilen, maar voor de hand liggend zijn die niet.

    Kijk ook uit met tussenberekeningen, die moeten namelijk ook in een 32-bits register van de CPU passen. Dus pow(2^32) gaat al fout, die veroorzaakt de overflow. Het maakt niet uit dat je er daarna nog 1 vanaf haalt.

    Bijdrager
    njdewit
    ”Buzz_D”

    Kijk ook uit met tussenberekeningen, die moeten namelijk ook in een 32-bits register van de CPU passen. Dus pow(2^32) gaat al fout, die veroorzaakt de overflow. Het maakt niet uit dat je er daarna nog 1 vanaf haalt.

    hehe, heb je helemaal gelijk in natuurlijk:) dat levert echter 0 op, en als je daar dan weer 1 vanaf haalt wrap je weer keurig naar max_int:D

    Bijdrager
    vikking

    Maar hoe zorg ik er dan voor dat een getal nooit groter kan worden dan 2^32? Want als ik gewoon in de for loop zet:
    [code:1:b7de9ecb56]if(c > max){
    printf("n");
    return 1;
    }[/code:1:b7de9ecb56]
    (met max = 0xffffffff) want als je dan bv het getal 2781789953 optelt met 3399308290 word dat gewoon 1886130947 en is het nog steeds kleiner dan max…

    Bijdrager
    iJoost
    ”njdewit”

    What the hell is that going to change? Toegegeven, het had leuk geweest als een long op 32-bit compilers keurig 64-bit zou zijn opgebroken in een low and high (d)word maar de realiteit is dat ze gewoon 32-bit zijn.

    (of doet apple’s gcc dat stiekem anders? danwel zie ik iets stoms over het hoofd)

    Weet ik veel. Er zijn zat C-compilers die longs hebben die langer zijn dan een int. Maar het hoeft niet inderdaad. Ik zal even voor je kijken… (hoewel je bijzonder vriendelijk bent.:-(

    Hier, op mijn iMac G5:

    [code:1:9fe14a3ca2][snow:~] hans% cat test.c
    #include <stdio.h>
    #include <limits.h>
    int main(){
    printf("%ldn",LONG_MAX);
    return 0;
    }
    [snow:~] hans% gcc -m64 test.c
    [snow:~] hans% ./a.out
    9223372036854775807
    [/code:1:9fe14a3ca2]

    Bijdrager
    njdewit

    dat werkt inderdaad niet, omdat die vergelijking nooit waar gaat zijn (je kijkt of het groter is dan 0xffffffff, maar dat kan dat getal feitelijk nooit worden, dan ben je al gewrapped)

    wat je moet doen is nadat je c uitrekent in het begin van je loop, kijken of deze kleiner dan/gelijk is aan b (dat is namelijk de c van je vorige iteratie), dan weet je dat a+b een getal groter dan 0xffffffff produceert (en dus wrapped) en je aan het einde van het bereik van je huidige aanpak zit

    dan break je gewoon je loop, zo:

    if (c <= b) break;

    Bijdrager
    njdewit
    ”iJoost”
    ”njdewit”

    What the hell is that going to change? Toegegeven, het had leuk geweest als een long op 32-bit compilers keurig 64-bit zou zijn opgebroken in een low and high (d)word maar de realiteit is dat ze gewoon 32-bit zijn.

    (of doet apple’s gcc dat stiekem anders? danwel zie ik iets stoms over het hoofd)

    Weet ik veel. Er zij zat C-compilers die longs hebben die langer zijn dan een int. Maar het hoeft niet inderdaad. Ik zal even voor je kijken… (hoewel je bijzonder vriendelijk bent.:-(

    Hier, op mijn iMac G5:

    [code:1:dcf63f0c75][snow:~] hans% cat test.c
    #include <stdio.h>
    #include <limits.h>
    int main(){
    printf("%ldn",LONG_MAX);
    return 0;
    }
    [snow:~] hans% gcc -m64 test.c
    [snow:~] hans% ./a.out
    9223372036854775807
    [/code:1:dcf63f0c75]

    Nou nou, zo onvriendelijk ben ik toch ook weer niet;) Maar verrek ja. Wat doet die -m64 parameter eigenlijk bij GCC?

    (zelfde testje levert onder 32-bit-mode VC7 een veel kleiner getal op btw, te weten ((2^32)/2)-1 :))

    Bijdrager
    iJoost

    Zucht… :sealed:

    Bijdrager
    njdewit
    ”iJoost”

    Zucht… :sealed:

    Ik stel je toch gewoon een legitieme vraag of wat is het probleem nou precies?

    Bijdrager
    iJoost

    Ik geef aan dat je onvriendelijk overkomt en je zegt niet sorry maar je ontkent. En vervolgens ben je te beroerd om te zelf de man open te trekken. Vind je het gek dat ik even afhaak?

    Bijdrager
    njdewit
    ”iJoost”

    Ik geef aan dat je onvriendelijk overkomt en je zegt niet sorry maar je ontkent. En vervolgens ben je te beroerd om te zelf de man open te trekken. Vind je het gek dat ik even afhaak?

    Ik had gehoopt dat je het niet zo zwaar op zou nemen, maar ik wil me er best voor excuseren (bij deze) want het kan inderdaad wel eens vriendelijker van mijn kant. Iedereen zijn nukken!

    Dan hoop ik dat dat bij deze uit de wereld is:)

    Bijdrager
    vikking

    [code:1:c7e3dc3fbb]#include <stdio.h>
    #include <limits.h>
    int main(){
    printf("%ldn",LONG_MAX);
    return 0;
    } [/code:1:c7e3dc3fbb]
    Geeft bij mij ook 9223372036854775807, maar als ik het gebruik in mijn progje, gaat gij toch maar evenver als de unsigned int…
    Die if (c <= b) break; werkt niet echt aangezien de eerste keer dat hij door die loop loopt c gelijk is aan 1, maar b is ook gelijk aan 1, dus gaat hij niet verder als de eerste 1. Ik heb er if (c < b) break; van gemaakt:)

    Bijdrager
    njdewit

    KUT:D dat had ik er eerst staan namelijk en dacht toen dat die gelijk aan case er ook wel even bij kon:) Da’s al de tweede stompzinnigheid van me, te meer omdat de < al voldeed in de reeks getallen en het dus niet eens toegevoegde waarde had.

    Wellicht kun je trouwens even kijken of je geen expliciete 64-bit types ter beschikking hebt. Of natuurlijk iets anders (nieuw experiment ofzo) gaan doen met je tijd;)

    Bijdrager
    vikking
    ”njdewit”

    Wellicht kun je trouwens even kijken of je geen expliciete 64-bit types ter beschikking hebt. Of natuurlijk iets anders (nieuw experiment ofzo) gaan doen met je tijd;)

    Mja, kga later als ik een grafisch rekenmachine heb, proberen het daarop te zetten, en volgens mij is die processor niet echt 64 bit;)

    ”njdewit”

    Of natuurlijk iets anders (nieuw experiment ofzo) gaan doen met je tijd;)

    Idd je hebt gelijk, maar omdat mijn C-skills niet zo goed zijn, wou ik wat dingen bijleren:)

    Bijdrager
    njdewit

    Dat hoeft in principe ook niet natuurlijk. Je rekenmachine zal op een gegeven moment wel op ‘infinity’ knallen ofzo:) Have fun iig.

    Idd je hebt gelijk, maar omdat mijn C-skills niet zo goed zijn, wou ik wat dingen bijleren

    Lijkt me redelijk geslaagd toch?:)

    Bijdrager
    vikking
    ”njdewit”

    Dat hoeft in principe ook niet natuurlijk. Je rekenmachine zal op een gegeven moment wel op ‘infinity’ knallen ofzo:) Have fun iig.

    Hoe bedoel je?

    ”njdewit”

    Idd je hebt gelijk, maar omdat mijn C-skills niet zo goed zijn, wou ik wat dingen bijleren

    Lijkt me redelijk geslaagd toch?:)

    Idd:)

    Bijdrager
    njdewit
    ”vikking”

    Hoe bedoel je?

    Nouja dat er altijd wel een limiet zit aan wat een X apparaat / stuk software weer kan geven:)

    Bijdrager
    iJoost
    ”vikking”

    Geeft bij mij ook 9223372036854775807, maar als ik het gebruik in mijn progje, gaat gij toch maar evenver als de unsigned int…

    Je moet je programma wel even omschrijven naar rekenen met longs. En je compiler die switch meegeven. (Als je Xcode gebruikt heb je hier misschien iets aan voor de juiste instelling.)

    Hier een misschien nog een iets overtuigender “bewijs” dat je gewoon kunt rekenen met 64 bit integers:

    [code:1:1a8309b8c1][snow:~] hans% cat test.c
    #include <stdio.h>
    #include <limits.h>
    int main(){
    int i;
    long j=1;
    for(i=0;i<64;i++){
    printf("%d: %ldn",i,j);
    j*=2;
    }
    return 0;
    }
    [snow:~] hans% gcc -m64 test.c
    [snow:~] hans% ./a.out
    0: 1
    1: 2
    2: 4
    3: 8
    4: 16
    5: 32
    6: 64
    7: 128
    8: 256
    9: 512
    10: 1024
    11: 2048
    12: 4096
    13: 8192
    14: 16384
    15: 32768
    16: 65536
    17: 131072
    18: 262144
    19: 524288
    20: 1048576
    21: 2097152
    22: 4194304
    23: 8388608
    24: 16777216
    25: 33554432
    26: 67108864
    27: 134217728
    28: 268435456
    29: 536870912
    30: 1073741824
    31: 2147483648
    32: 4294967296
    33: 8589934592
    34: 17179869184
    35: 34359738368
    36: 68719476736
    37: 137438953472
    38: 274877906944
    39: 549755813888
    40: 1099511627776
    41: 2199023255552
    42: 4398046511104
    43: 8796093022208
    44: 17592186044416
    45: 35184372088832
    46: 70368744177664
    47: 140737488355328
    48: 281474976710656
    49: 562949953421312
    50: 1125899906842624
    51: 2251799813685248
    52: 4503599627370496
    53: 9007199254740992
    54: 18014398509481984
    55: 36028797018963968
    56: 72057594037927936
    57: 144115188075855872
    58: 288230376151711744
    59: 576460752303423488
    60: 1152921504606846976
    61: 2305843009213693952
    62: 4611686018427387904
    63: -9223372036854775808
    [/code:1:1a8309b8c1]

    Bijdrager
    njdewit

    Daar twijfelde niemand toch ook aan? ’t Moet alleen wel even system/compiler/runtime-halve enabled zijn:) Kweet niet wat vikking precies gebruikt voor systeem/software?

    Lees net voor ’t eerst dat de G5 64-bit is trouwens, shows what I know:D

    Bijdrager
    vikking

    Hmmzzz, volgens mij is er dan iets met mijn compiler, als ik dat programma van ijoost laat lopen krijg ik dit:

    0: 1
    1: 2
    2: 4
    3: 8
    4: 16
    5: 32
    6: 64
    7: 128
    8: 256
    9: 512
    10: 1024
    11: 2048
    12: 4096
    13: 8192
    14: 16384
    15: 32768
    16: 65536
    17: 131072
    18: 262144
    19: 524288
    20: 1048576
    21: 2097152
    22: 4194304
    23: 8388608
    24: 16777216
    25: 33554432
    26: 67108864
    27: 134217728
    28: 268435456
    29: 536870912
    30: 1073741824
    31: -2147483648
    32: 0
    33: 0
    34: 0
    35: 0
    36: 0
    37: 0
    38: 0
    39: 0
    40: 0
    41: 0
    42: 0
    43: 0
    44: 0
    45: 0
    46: 0
    47: 0
    48: 0
    49: 0
    50: 0
    51: 0
    52: 0
    53: 0
    54: 0
    55: 0
    56: 0
    57: 0
    58: 0
    59: 0
    60: 0
    61: 0
    62: 0
    63: 0

30 berichten aan het bekijken - 1 tot 30 (van in totaal 44)

Je moet ingelogd zijn om een reactie op dit onderwerp te kunnen geven.