You are invited to Log in or Register a free Frihost Account!

# 10 frih\$ contest: what does this c++ code do?

wernichtfragt
 Code: int main() {    long int   yoko[1000];          yoko[0] = 2;    int      john=1,paul=1;    bool      ringo; while(john < 999) {    paul +=2;    ringo = true;    for(int x=0; x

the 10frih\$-question is: which special series of numbers is in yoko[] after the first run of the code?

you may comment the code/ ask questions if you like!

i would actually appreciate if one of you could post an analog sourcecode of this in Assembly language (receives another 10 frih \$)
Indi
(Are you sure that you got that code right? It invokes undefined behaviour. There's no way to predict what results you're going to get. Perhaps you meant to set john to 0 and not 1 right at the beginning?)

(Edit: or maybe you meant for "ringo = ringo && (!!(yoko[john] % paul));" to be "ringo = ringo && (!!(yoko[x] % paul));"?)
wernichtfragt
yes, little mistake..... happens again and again.... now its correct
umeshtangnu
 wernichtfragt wrote: int main() { long int yoko[1000]; yoko[0] = 2; int john=1,paul=1; bool ringo; while(john < 999) { paul +=2; ringo = true; for(int x=0; x

 Code: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325 327 329 331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 385 387 389 391 393 395 397 399 401 403 405 407 409 411 413 415 417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 449 451 453 455 457 459 461 463 465 467 469 471 473 475 477 479 481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 513 515 517 519 521 523 525 527 529 531 533 535 537 539 541 543 545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 577 579 581 583 585 587 589 591 593 595 597 599 601 603 605 607 609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 641 643 645 647 649 651 653 655 657 659 661 663 665 667 669 671 673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 705 707 709 711 713 715 717 719 721 723 725 727 729 731 733 735 737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 769 771 773 775 777 779 781 783 785 787 789 791 793 795 797 799 801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 833 835 837 839 841 843 845 847 849 851 853 855 857 859 861 863 865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 897 899 901 903 905 907 909 911 913 915 917 919 921 923 925 927 929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 961 963 965 967 969 971 973 975 977 979 981 983 985 987 989 991 993 995 997 999 1001 1003 1005 1007 1009 1011 1013 1015 1017 1019 1021 1023 1025 1027 1029 1031 1033 1035 1037 1039 1041 1043 1045 1047 1049 1051 1053 1055 1057 1059 1061 1063 1065 1067 1069 1071 1073 1075 1077 1079 1081 1083 1085 1087 1089 1091 1093 1095 1097 1099 1101 1103 1105 1107 1109 1111 1113 1115 1117 1119 1121 1123 1125 1127 1129 1131 1133 1135 1137 1139 1141 1143 1145 1147 1149 1151 1153 1155 1157 1159 1161 1163 1165 1167 1169 1171 1173 1175 1177 1179 1181 1183 1185 1187 1189 1191 1193 1195 1197 1199 1201 1203 1205 1207 1209 1211 1213 1215 1217 1219 1221 1223 1225 1227 1229 1231 1233 1235 1237 1239 1241 1243 1245 1247 1249 1251 1253 1255 1257 1259 1261 1263 1265 1267 1269 1271 1273 1275 1277 1279 1281 1283 1285 1287 1289 1291 1293 1295 1297 1299 1301 1303 1305 1307 1309 1311 1313 1315 1317 1319 1321 1323 1325 1327 1329 1331 1333 1335 1337 1339 1341 1343 1345 1347 1349 1351 1353 1355 1357 1359 1361 1363 1365 1367 1369 1371 1373 1375 1377 1379 1381 1383 1385 1387 1389 1391 1393 1395 1397 1399 1401 1403 1405 1407 1409 1411 1413 1415 1417 1419 1421 1423 1425 1427 1429 1431 1433 1435 1437 1439 1441 1443 1445 1447 1449 1451 1453 1455 1457 1459 1461 1463 1465 1467 1469 1471 1473 1475 1477 1479 1481 1483 1485 1487 1489 1491 1493 1495 1497 1499 1501 1503 1505 1507 1509 1511 1513 1515 1517 1519 1521 1523 1525 1527 1529 1531 1533 1535 1537 1539 1541 1543 1545 1547 1549 1551 1553 1555 1557 1559 1561 1563 1565 1567 1569 1571 1573 1575 1577 1579 1581 1583 1585 1587 1589 1591 1593 1595 1597 1599 1601 1603 1605 1607 1609 1611 1613 1615 1617 1619 1621 1623 1625 1627 1629 1631 1633 1635 1637 1639 1641 1643 1645 1647 1649 1651 1653 1655 1657 1659 1661 1663 1665 1667 1669 1671 1673 1675 1677 1679 1681 1683 1685 1687 1689 1691 1693 1695 1697 1699 1701 1703 1705 1707 1709 1711 1713 1715 1717 1719 1721 1723 1725 1727 1729 1731 1733 1735 1737 1739 1741 1743 1745 1747 1749 1751 1753 1755 1757 1759 1761 1763 1765 1767 1769 1771 1773 1775 1777 1779 1781 1783 1785 1787 1789 1791 1793 1795 1797 1799 1801 1803 1805 1807 1809 1811 1813 1815 1817 1819 1821 1823 1825 1827 1829 1831 1833 1835 1837 1839 1841 1843 1845 1847 1849 1851 1853 1855 1857 1859 1861 1863 1865 1867 1869 1871 1873 1875 1877 1879 1881 1883 1885 1887 1889 1891 1893 1895 1897 1899 1901 1903 1905 1907 1909 1911 1913 1915 1917 1919 1921 1923 1925 1927 1929 1931 1933 1935 1937 1939 1941 1943 1945 1947 1949 1951 1953 1955 1957 1959 1961 1963 1965 1967 1969 1971 1973 1975 1977 1979 1981 1983 1985 1987 1989 1991 1993 1995 1997

disassembly
 Code: int main() { 0041D220  push        ebp  0041D221  mov         ebp,esp 0041D223  push        0FFFFFFFFh 0041D225  push        offset __ehhandler\$_main (44F2FBh) 0041D22A  mov         eax,dword ptr fs:[00000000h] 0041D230  push        eax  0041D231  mov         dword ptr fs:[0],esp 0041D238  mov         eax,115Ch 0041D23D  call        @ILT+1010(__chkstk) (41B3F7h) 0041D242  push        ebx  0041D243  push        esi  0041D244  push        edi  0041D245  lea         edi,[ebp-1168h] 0041D24B  mov         ecx,457h 0041D250  mov         eax,0CCCCCCCCh 0041D255  rep stos    dword ptr [edi]    long int   yoko[1000];    yoko[0] = 2; 0041D257  mov         dword ptr [yoko],2    int      john=1,paul=1; 0041D261  mov         dword ptr [john],1 0041D26B  mov         dword ptr [paul],1    bool      ringo;    int y=0; 0041D275  mov         dword ptr [y],0 int z=1/y; 0041D27F  mov         eax,1 0041D284  cdq              0041D285  idiv        eax,dword ptr [y] 0041D28B  mov         dword ptr [z],eax    while(john < 999) 0041D291  cmp         dword ptr [john],3E7h 0041D29B  jge         main+139h (41D359h)    {       paul +=2; 0041D2A1  mov         eax,dword ptr [paul] 0041D2A7  add         eax,2 0041D2AA  mov         dword ptr [paul],eax       ringo = true; 0041D2B0  mov         byte ptr [ringo],1       for(int x=0; x >::basic_ofstream > (41BE01h) 0041D366  mov         dword ptr [ebp-4],0    file.open ("a.txt",ios::trunc); 0041D36D  push        1B6h 0041D372  push        10h  0041D374  push        offset string "a.txt" (4530CCh) 0041D379  lea         ecx,[file] 0041D37F  call        std::basic_ofstream >::open (41BAB4h)    for (int i=0;i<999;i++) 0041D384  mov         dword ptr [i],0 0041D38E  jmp         main+17Fh (41D39Fh) 0041D390  mov         eax,dword ptr [i] 0041D396  add         eax,1 0041D399  mov         dword ptr [i],eax 0041D39F  cmp         dword ptr [i],3E7h 0041D3A9  jge         main+1B4h (41D3D4h)    {       file< >::operator<< (41B5F5h) 0041D3C9  push        eax  0041D3CA  call        std::operator<< > (41BAC3h) 0041D3CF  add         esp,8    } 0041D3D2  jmp         main+170h (41D390h) } 0041D3D4  mov         dword ptr [ebp-4],0FFFFFFFFh 0041D3DB  lea         ecx,[file] 0041D3E1  call        std::basic_ofstream >::`vbase destructor' (41B48Dh) 0041D3E6  xor         eax,eax 0041D3E8  push        edx  0041D3E9  mov         ecx,ebp 0041D3EB  push        eax  0041D3EC  lea         edx,ds:[41D417h] 0041D3F2  call        @ILT+1390(@_RTC_CheckStackVars@8) (41B573h) 0041D3F7  pop         eax  0041D3F8  pop         edx  0041D3F9  mov         ecx,dword ptr [ebp-0Ch] 0041D3FC  mov         dword ptr fs:[0],ecx 0041D403  pop         edi  0041D404  pop         esi  0041D405  pop         ebx  0041D406  add         esp,1168h 0041D40C  cmp         ebp,esp 0041D40E  call        @ILT+3255(__RTC_CheckEsp) (41BCBCh) 0041D413  mov         esp,ebp 0041D415  pop         ebp  0041D416  ret              0041D417  db          02h  0041D418  db          00h  0041D419  db          00h  0041D41A  db          00h  0041D41B  db          1fh  0041D41C  db          d4h  0041D41D  db          41h  0041D41E  db          00h  0041D41F  db          50h  0041D420  db          f0h  0041D421  db          ffh  0041D422  db          ffh  0041D423  db          a0h  0041D424  db          0fh  0041D425  db          00h  0041D426  db          00h  0041D427  db          3ch  0041D428  db          d4h  0041D429  db          41h  0041D42A  db          00h  0041D42B  db          6ch  0041D42C  db          efh  0041D42D  db          ffh  0041D42E  db          ffh  0041D42F  db          94h  0041D430  db          00h  0041D431  db          00h  0041D432  db          00h  0041D433  db          37h  0041D434  db          d4h  0041D435  db          41h  0041D436  db          00h  0041D437  db          66h  0041D438  db          69h  0041D439  db          6ch  0041D43A  db          65h  0041D43B  db          00h  0041D43C  db          79h  0041D43D  db          6fh  0041D43E  db          6bh  0041D43F  db          6fh  0041D440  db          00h

but i had modified you code so that i could get the out put

 Code: int main() {    long int   yoko[1000];    yoko[0] = 2;    int      john=1,paul=1;    bool      ringo;    while(john < 999)    {       paul +=2;       ringo = true;       for(int x=0; x
wernichtfragt
@umeshtangnu

yep thats correct ;)

the code is in fact a "prime number generator"

int y=0;
0041D275 mov dword ptr [y],0
int z=1/y;
0041D27F mov eax,1
0041D284 cdq
0041D285 idiv eax,dword ptr [y]
0041D28B mov dword ptr [z],eax

^^ what the heck does this do?
i cannot find an proper explanation since
1) 1 /0 equals infinity = impossible value for dword
2) y, z both are never used again in the code
so why did the compiler do this?

i wonder if some tweaking of the asm code could speed up this any more?

Indi
umeshtangnu wrote:
 Code: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 etc.

 wernichtfragt wrote: @umeshtangnu yep thats correct thanks... heres your 20 frih\$ the code is in fact a "prime number generator"

Excuse me for pointing out the obvious. ^_^; But 9, 15, 21, 25, and many others in that list are not prime numbers. Except for the number 2 - which you assign explicitly with "yoko[0] = 2;" - it is simply a sequential list of odd numbers, generated by the lines "paul +=2;" and "yoko[john] = paul;".

If you were to change the line "yoko[0] = 2;" to read "yoko[0] = 1;", you would, in fact, have a list of positive odd numbers.

Of course, the assembly for a program to allocate an array of 1000 ints on the stack and fill them with sequential odd numbers is trivial... a whole lot smaller than what you got there. ^_^;
imagefree
 wernichtfragt wrote: int main() { long int yoko[1000]; yoko[0] = 2; int john=1,paul=1; bool ringo; while(john < 999) { paul +=2; ringo = true; for(int x=0; x

I dont need your points but i there are some problems in code (i think).
I stopped learning c 5 years back and since then i have never made a c program.

I think there are some mistakes in this code that you wrote ";" after every "}". I think this syntax is wrong (May be it is rite in c++)

But the main problem is your prime # generator is generating some numbers like 9, 15 etc. These are not prime.

When i was 16, i used to make more complax prime# software in c using just the basics.
wernichtfragt
yes another mistake by me
ringo = ringo && (!!(yoko[x] % paul));
is wrong, replace by
ringo = ringo && (!!(paul % yoko[x]));

then it will work
Indi
 imagefree wrote: I think there are some mistakes in this code that you wrote ";" after every "}". I think this syntax is wrong (May be it is rite in c++)

It's neither right nor wrong in either C or C++. It's just that those semicolons are not necessary. They don't do any harm, but they don't do any good either.
wernichtfragt
357.686.312.646.216.567.629.137
this number is prime
you can can remove the most left digit
and the remaining number is still prime
you can repeat this until you reach 7, which is prime too, course

1000000000000000000000000000000000000000000000000000000000007
my favourite prime (10^60+7)
qebab
http://pastebin.mozilla.org/62550

This may or may not be good coding practise (And it has no comments et al.), but it runs and it seems correct. This is the Sieve of Erastothenes. I just started learning (Or trying to, anyway) C++ the day before yesterday, so I didn't dare to try deciphering your program.

Incidentally, you aren't a regular on Project Euler? If you like primes, that's probably not a bad place to hang around.

Edit: The forum ruined my beautiful format on the code the brackets were perfectly aligned.

Edit 2: Indi, you seem to have a lot of knowledge about the C family of languages. You don't happen to know a good IDE for C++ that runs under linux? I'm using emacs so far, but it's more a text editor (No matter how extensive it is) than an IDE, so I'm probably going to run into some shortcomings sooner or later.

Edit 3 - Will it never end?!: Moved it to a pastebin.
Indi
 qebab wrote: http://pastebin.mozilla.org/62550 This may or may not be good coding practise (And it has no comments et al.), but it runs and it seems correct. This is the Sieve of Erastothenes. I just started learning (Or trying to, anyway) C++ the day before yesterday, so I didn't dare to try deciphering your program.

Just FYI, the construct on line 8 is not legal in C++. The ability to create runtime sized arrays was added in the 1999 standardization of C (C99). Unfortunately, C++ was standardized in 1998, and is built roughly on top of the 1989 C standard, so all the neat stuff that was added in 1999 didn't make it into C++.

As far as i recall, gcc by default allows you to make dynamic arrays as an extension. That's why your code compiles. You can turn this (and other gcc extensions) off by using either -ansi or -pendantic (i can't remember which).

If you want to make your code C++ legal, all you would have to do is add an "#include <vector>" and replace line 8 with "std::vector<int> list(n);".

Otherwise, looks great.

 qebab wrote: Edit 2: Indi, you seem to have a lot of knowledge about the C family of languages. You don't happen to know a good IDE for C++ that runs under linux? I'm using emacs so far, but it's more a text editor (No matter how extensive it is) than an IDE, so I'm probably going to run into some shortcomings sooner or later.

i don't use IDEs if i can avoid it. i just use a syntax highlighting text editor and make my own makefiles.
wernichtfragt
yeah your implementation of the sieve algorithm looks great
thats how we estimated primes back in elementary school
and i think its faster than my first approach
but the memory consumption is enormous
qebab
 Indi wrote: Just FYI, the construct on line 8 is not legal in C++. The ability to create runtime sized arrays was added in the 1999 standardization of C (C99). Unfortunately, C++ was standardized in 1998, and is built roughly on top of the 1989 C standard, so all the neat stuff that was added in 1999 didn't make it into C++.

Ah, that is good to know.

 Indi wrote: As far as i recall, gcc by default allows you to make dynamic arrays as an extension. That's why your code compiles. You can turn this (and other gcc extensions) off by using either -ansi or -pendantic (i can't remember which).

The man page is telling me pedantic here. I'll keep that in mind.

 Indi wrote: If you want to make your code C++ legal, all you would have to do is add an "#include " and replace line 8 with "std::vector list(n);".

Okay, so this is like a more dynamic array? (I'll read up on it)
Sort of like what would be called a list in LISP/Python? Does it allow multiple dimensions?

 Indi wrote: i don't use IDEs if i can avoid it. i just use a syntax highlighting text editor and make my own makefiles.

That's what I have been doing so far, but I'm thinking that a proper IDE might help me catch a few more of my errors before I try to compile, and a quick way to look up functions from the standard library would certainly be very nice. I'm going to go to the library and pick up a book and a reference sometime after my exams are finished though, and they might be better tools. It's probably not a half bad idea to learn a language without an IDE that does half of the work for me; I might end up remembering and understanding things better.
qebab
 wernichtfragt wrote: but the memory consumption is enormous

That depends on how you define enormous, I believe. I tested it out a bit a minute ago, and I personally define 250 kb as reasonable with todays computers. It might have been different some years back, but that is 250 kb, while the free memory pool on my laptop is 750 000 kb right now.
Indi
 qebab wrote: Okay, so this is like a more dynamic array? (I'll read up on it) Sort of like what would be called a list in LISP/Python?

Yes, it's exactly like a dynamic array - i don't know Python well enough to know whether std::vector<T> or std::list<T> is closer to the Python list.

The only downside of using vector instead of an array is that vector dynamically allocates the space it needs using new instead of just using the stack. Usually that's a good thing, but for small, fixed-size arrays it can be wasteful. But until C++ supports C99 runtime-sized arrays, it's the best we can do.

 qebab wrote: Does it allow multiple dimensions?

Yes it does, it supports "ragged" multidimensional arrays. A non-ragged array is one that looks like this (in two dimensions):

 Code: Dimension 1 -> 0 1 2 3 4 5 Dimension 2 v        0       a b c d e f        1       g h i j k l        2       m n o p q r        3       s t u v w x

But a ragged array can do this:

 Code: Dimension 1 -> 0 1 2 3 4 5 Dimension 2 v        0       a b c d e f        1       g h i        2       j        3       k l m n o        4       p q        5       r s t u v w

To make a multidimensional vector, you just nest vectors: "std::vector<std::vector<int> >", and you can go for as many dimensions as you like. And of course, you access them just like how you're used to: "a[n][m];".

If you don't want a ragged array, and need some more speed, you have several options, including writing your own multidimensional array class, using std::tr1::array<T, N> (or boost::array<T, N>, same thing), and many more.
snicker
 wernichtfragt wrote: skip the code is in fact a "prime number generator" skip

Actually, a prime number generator is something like the Graal in mathematics... given a number, how to find an algorithm that determines the next prime (without extensively trying to divide it by the numbers preceding it, of course)? Does an algorithm like this even exist?

My 2 cents
wernichtfragt
there are better tests for primality // dividing by all preceding numbers is the just the simplest method

http://en.wikipedia.org/wiki/Primality_test