Problem mit einem kompliziertem Ausdruck



  • unsigned snoob( unsigned x ) 
    {
    unsigned smallest , ripple , ones;			/* Definiert 3 Variablen vom Typ unsigned int */
    smallest = x & -x;							/* smallest erhaelt den groessten Teiler von x, der eine Potenz von 2 ist */
    ripple = x + smallest;						/* ripple erhaelt den Wert von x addiert mit smallest */
    ones = x ^ ripple;							/**/
    ones = (ones >> 2)/smallest;
    return ripple | ones;
    }
    

    Es geht konkret um:

    ones = x ^ ripple;							
    ones = (ones >> 2)/smallest;
    

    Ich habe jetzt händisch mit ein paar zufälligen werten probiert, was genau die Funktion machen könnte , ich komme aber nicht drauf, da mir die beiden Ausdrücke nicht genau verraten, was sie machen.

    smallest = x & -x;
    

    habe ich rausbekommen.

    Könnt ihr mir vielleicht auf die Sprünge helfen?

    Vielen lieben Dank



  • wgerhtrj schrieb:

    Es geht konkret um:

    ones = x ^ ripple;							
    ones = (ones >> 2)/smallest;
    

    Ich habe jetzt händisch mit ein paar zufälligen werten probiert, was genau die Funktion machen könnte

    😮 Warum probieren? Hast du den ganzen Rest auch nur ausprobiert? Man kann sowas auch nachlesen.

    https://www.google.de/search?q=c+operatoren



  • Hallo Bashar 🙂
    Na klar kenne ich die Operationen.

    Es geht konkret darum, herauszufinden, was die Funktion snoob macht.
    Ich habe mir auch ne schleife gebaut, und einn paar werte eingegeben und geschaut, was die einzelnen Ausdrücke machen.

    smallest = x & -x;
    

    Dies gibt mir zum Beispiel den größten teiler von x, der eine Potenz von 2 ist.
    Bsp: x = 2, smallest = 2;
    x = 14, smallest = 2;
    x = ungerade, smallest = 1;

    Ich komme aber mir probieren nicht heraus, was die Funktion konkret macht.
    Hier mal eine ausgabe für alle Zweierpotenzen, mit 2 beginnend und 512 endend:

    smallest    2
    ripple    4
    ones    6
    ones    0
    snoob     4
    
    1
    smallest    4
    ripple    8
    ones    12
    ones    0
    snoob     8
    
    1
    smallest    8
    ripple    16
    ones    24
    ones    0
    snoob     16
    
    1
    smallest    16
    ripple    32
    ones    48
    ones    0
    snoob     32
    
    1
    smallest    32
    ripple    64
    ones    96
    ones    0
    snoob     64
    
    1
    smallest    64
    ripple    128
    ones    192
    ones    0
    snoob     128
    
    1
    smallest    128
    ripple    256
    ones    384
    ones    0
    snoob     256
    
    1
    smallest    256
    ripple    512
    ones    768
    ones    0
    snoob     512
    
    1
    smallest    512
    ripple    1024
    ones    1536
    ones    0
    snoob     1024
    

    Die 1en am Anfang ignorieren bitte, die waren nur dazu da, auf Tastendruck den nächsten Schritt einzuleiten.



  • Mir erschließt sich der Sinn der Aufgabe nicht.

    unsigned snoob( unsigned x )
    {
    //x=*****0111000 //statt 3 auch beliebig viele aber mindestens eine
    unsigned smallest , ripple , ones;          /* Definiert 3 Variablen vom Typ unsigned int */
    smallest = x & -x;                          /* smallest erhaelt den groessten Teiler von x, der eine Potenz von 2 ist */
    //s=000000001000 //letze 1
    ripple = x + smallest;                      /* ripple erhaelt den Wert von x addiert mit smallest */
    //r=*****1000000 //rechteste einergruppe nullen, links davon eine 1 machen
    ones = x ^ ripple;                          /**/
    //o=000001111000 //nur die rechteste einergruppe und daneben eine 1 überleben
    ones=ones/smallest;
    //o=000000001111 //und sie wird an den rechten rand geschoben
    ones = ones >> 2;
    //o=000000000011 //einergruppe am rechten rand, hat eine 1 weniger als die rechteste
    	//einergruppe von x
    //o=000000011110
    return ripple | ones;
    //such die rechteste einergruppe
    //verschiebe ihre linke 1 um eine stelle nach links
    //verschiebe die anderen 1-en bis an den rand nach rechts
    }
    
    1 10
    10 100
    11 101
    100 1000
    101 110
    110 1001
    111 1011
    1000 10000
    1001 1010
    1010 1100
    1011 1101
    1100 10001
    1101 1110
    1110 10011
    1111 10111
    10000 100000
    10001 10010
    10010 10100
    10011 10101
    …
    1100100 1101000
    1100101 1100110
    1100110 1101001
    1100111 1101011
    1101000 1110000
    1101001 1101010
    1101010 1101100
    1101011 1101101
    1101100 1110001
    1101101 1101110
    1101110 1110011
    1101111 1110111
    1110000 10000011
    1110001 1110010
    1110010 1110100
    1110011 1110101
    1110100 1111000
    1110101 1110110
    1110110 1111001
    1110111 1111011
    


  • x=7;
    solange x<=(7<<3);
    x=snoob(x);

    zählt die (6 über 3) möglichkeiten auf, 3 bits von 6 zu setzen.

    000111
    001011
    001101
    001110
    010011
    010101
    010110
    011001
    011010
    011100
    100011
    100101
    100110
    101001
    101010
    101100
    110001
    110010
    110100
    111000
    


  • Hallo volkard.

    Mir erschließt sich der Sinn der Aufgabe nicht.

    Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
    Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

    Mir erschließt sich der Sinn der Aufgabe nicht.

    Soll ich dir mal ein paar Aufgaben zeigen?
    zB:

    int x = 10, y = 20;
    x = x++ + y++;
    y = ++y + ++x;
    

    Frage: Welche Werte haben x und y?
    Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
    Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
    Ich so: wtf..??!!



  • Dein Lehrer hat keine Ahnung.
    Da musst du leider mit leben.
    Du kannst dich aber gleich daran gewöhnen, dass es im Leben oftmals Leute gibt, die von Dingen reden, von den sie keine Ahnung haben. Das hindert sie aber nicht daran, darüber zu reden, oftmals sogar sehen sie ihre Berufung darin, von Dingen zu reden, von denen sie keine Ahnung haben: Politiker,Manager,Lehrer,...



  • wgerhtrj schrieb:

    Hallo volkard.

    Mir erschließt sich der Sinn der Aufgabe nicht.

    Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
    Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

    Ich meinte, was erwartet er, was Ihr davon lernt? Das ist doch keine lehrreiche Aufgabe, sondern schlichtes "Ich zeige Euch mal, daß ich viel schlauer bin".

    wgerhtrj schrieb:

    Mir erschließt sich der Sinn der Aufgabe nicht.

    Soll ich dir mal ein paar Aufgaben zeigen?
    zB:

    int x = 10, y = 20;
    x = x++ + y++;
    y = ++y + ++x;
    

    Frage: Welche Werte haben x und y?

    dito.

    wgerhtrj schrieb:

    Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
    Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
    Ich so: wtf..??!!

    Leicht bessere Chanchen gehabt, wenn Du ein gut googlebares Wort wir Sequenzpunkte eingebaut hättest. In der Schule kann man gegen sowas noch den Aufstand proben…
    Aber im Studium nicht mehr, da hat der Prof einfach Recht. Selbst vor Gericht, was könnte der Richter anderes machen, als den Prof fragen?
    Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

    Am besten, Du übst schonmal. Immer hübsch rausfinden, was er für Sachen falsch macht und die Antwort finden, auf die er am sichersten die volle Punktzahl gibt.



  • wgerhtrj schrieb:

    Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

    Jo, Gosper's Algorithm ist auch was total anderes. "An Algorithm for finding closed form Hypergeometric Identities."

    Für den Gosper's-Hack gibt es anscheinend inzwischen bessere Implementierungen, hier einer, der noch die Ursprüngliche Form nimmt.
    http://read.seas.harvard.edu/cs207/2012/?p=64





  • volkard schrieb:

    Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

    Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.



  • Bashar schrieb:

    volkard schrieb:

    Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

    Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

    Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

    Das Fach war "Datensicherheit" oder sowas bei einem Lehrbeauftragten. Teil des Spezialisierungsschwerpunkts "Datenschutz". Helau, wer modernistisch tagesaktuellen unausgegorenen Schott belegt, und mehr Semesterwochenstunden abrockt, als sein müssten, verschwendet nicht nur seine Zeit, sondern senkt auch noch seine Note. Ähnliche Dinger gab es in jedem anderen Fach dieses Spezialisierungsschwerpunkts, außer bei "Kryptologie", das hielt eine Mathe-Prof. Da hätte ich beinahe eine 2 gekriegt, aber das war allein meine Schuld.

    Es ging darum, uns Idioden-Studenten ein wenig begreiflich zu machen, daß es so manche Sachen gibt, die eher harmlos zu berechnen sind und manche, da steht man davor wie vor einer Wand. Lehrinhalte quasi aus der c't kopiert und wenn's nicht reicht, auch mal die Computerbild.

    Sah ungefähr wir folgt aus:
    (Hab schonmal angekreuzt, bei 'f' waren wir anderer Meinung.)

    Bitte ankreuzen:
    
    Die Funktion f ist...
    
    f(x)    |  konstant | linear | quadratisch | polynomisch | exponentiell 
    -----------------------------------------------------------------------
      2^x   |           |        |             |             |     x
    -----------------------------------------------------------------------
       5    |     x     |        |             |      f      |
    -----------------------------------------------------------------------
      x^2   |           |        |      x      |      x      |
    -----------------------------------------------------------------------
       x^3  |           |        |             |      x      |
    -----------------------------------------------------------------------
       x    |           |    x   |             |      f      |
    -----------------------------------------------------------------------
    (2^x)/x |           |        |             |             | x //wer die 1 verdient
    -----------------------------------------------------------------------
    

    🤡



  • volkard schrieb:

    Bashar schrieb:

    volkard schrieb:

    Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

    Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

    Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

    Ja, aber vielleicht kein Polynom (hängt von der vereinbarten Schreibweise ab).

    (Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.)

    Aber da es bei dir anscheinend um Komplexitätsklassen ging, kann es das eher nicht gewesen sein 🙂 BTW das ist komisch, weil polynomiale Laufzeit ja lediglich bedeutet, dass die Laufzeit asymptotisch durch ein Polynom beschränkt ist, also ist sogar log, Wurzel, Sinus etc. polynomiell, insbesondere natürlich 5 und x.



  • Abgesehen von dem Problemchen damals…

    Bashar schrieb:

    Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.

    Leuchtet mir sofort ein. Mir fällt nur gerade kein Fall ein. Bin wohl zu fest damit verhaftet, als Grundmenge die Reellen Zahlen zu nehmen.

    Nehmen wir als Definition des Polynoms mal
    http://de.wikipedia.org/wiki/Polynom#Definition

    Kannste mir auf die Schnelle mal ein Beispiel liefern, damit ich darüber träumen kann? (Bin im Umzug, Fernseher weg, vermutlich endgültig, Mathe-Träumen ist gut, mach ich schon die letzten drei Tage.)



  • Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf F2\mathbb{F}_2) überall 0.



  • Bashar schrieb:

    Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf F2\mathbb{F}_2) überall 0.

    lol!
    klar.



  • Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

    Überhaupt: 5 = 0 * x2 + 5 ist auch quadratisch, und in welcher Mathematik bitte ist 2x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.



  • seldon schrieb:

    Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

    Uups, übersehen. http://de.wikipedia.org/wiki/Lineare_Funktion

    seldon schrieb:

    Überhaupt: 5 = 0 * x2 + 5 ist auch quadratisch,

    Nö, das dann doch nicht.
    http://de.wikipedia.org/wiki/Quadratische_Funktion

    seldon schrieb:

    und in welcher Mathematik bitte ist 2x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.

    Haste sie jetzt nur zwischen x=-2 und x=2 plotten lassen?
    Also ich würde mal sagen 1.99^x < 2^x/x < 2^x für alle x>=1453, insofern ist sie mir für Komplexitätsüberlegungen exponentiell genug. Ist sie nicht?



  • Jaaaa...bei der quadratischen Funktion muss ich dir Recht geben. Ich hatte, zugegeben, nicht auf dem Schirm, dass a != 0 gefordert ist.

    Bei der Exponentialfunktion sehe ich die Dinge dann aber doch anders. Ob eine Funktion eine Exponentialfunktion ist, hat erstmal wenig mit Komplexitätsklassen zu tun, und 2x / x verhält sich in vielen Dingen anders als Exponentialfunktionen.

    Wenn wir über Komplexitätsklassen reden wollen, sieht die Sache wieder ganz anders aus -- da sprechen wir ja größtenteils über Teilmengen. Eine Funktion, die zeitlich mit Θ(2x / x) skaliert, ist in EXPTIME, aber das ist mit 5, x, x2 und x3 auch der Fall. f(x) in O(1) impliziert f(x) in O(n2), aber f(x) in Θ(2x/x) impliziert f(x) nicht in Θ(2x), und beide dieser Dinge implizieren f(x) nicht in Θ(1.99x). Was ist also unser Kriterium?


Log in to reply