[PASCAL] Machtsverheffen?

[Karp]

Mijn zeer intelligente informatica leraar kwam met een opdracht

Zet een binair getal om naar decimaal in Pascal

Hij leert ons de basis van Pascal en dan mogen we aan de slag

* Karp bedenkt een mooi PSD'tje
* Karp gaat aan het werk

en wat ziet ik?
Pascal kan geen machtsverheffen?!
Ik heb gezocht en gezocht maar nergens gevonden hoe dit moet
Zelfs geen alternatieve subroutine of functie of watooit

Kan iemand me hierbij helpen?

[Grum]

sorry maar een functie als 'pow' is echt wel simpel zelf te maken EN te bedenken.

[RickN]

Je moet gewoon een algoritme schrijven waarin je niet hoeft te machtsverheffen. Helemaal niet zo moeilijk hoor en ook een stuk efficienter.

Hint: Je hebt wel een hoop machten van 2 nodig, maar niet in een willekeurige volgorde. Sterker nog je hebt ze nodig in de volgorde: 1,2,4,8,16,32,... Oftewel, je kunt ze allemaal krijgen door met 1 te beginnen en dan met 2 te vermenigvuldigen als je een nieuwe nodig hebt.

[Verwijderd]

tip pascal kent wel shl en shr volgens mij?

[El_BingO]

Stel je hebt 2 tot de macht 3, dan doe je toch gewoon 2x2x2. Dus dat is oer simpel.
Daar kan je wel een formule van maken, met een variabele grondtal en en een variabele exponent.

[WOmBaT]

code:

Function Pow(Base, Exponent: integer): integer;
  Begin
    if Exponent = 0 then
    result := 1
    else
    result := Base * Pow(Base, Exponent - 1);
  End;

1 van de duizend die je met google kunt vinden

[Verwijderd]

A^B = exp(A*ln()

Beter opletten bij wiskunde .

[Bergen]

En de functie Power van de unit Math dan? Of zit dat alleen in Delphi? Pascal heb ik vroeger overgeslagen.. ik prutste met QBasic

[Soultaker]

De door Wombat gegeven oplossing is nogal inefficient als het om grote getallen gaat, aangezien je ongeveer evenveel recursieve aanroepen doet als je exponent groot is. (Maar dat was natuurlijk zijn punt niet).

Bij deze dus een leuker vraagstuk: bedenk een algoritme met een lagere complexiteit maar dezelfde werking.

En de volgende keer wat beter zoeken en/of zelf nadenken, alsjeblieft!

[lordsnow]

Beetje pseudo-code:


PowersTable := [1, 2, 4, .... , 4294967296];

For F = 1 TO 32 DO
shiftr(BinNumber)
IF carry = 1 THEN DecNumber := DecNumber + PowersTable[F]
NEXT F

[Verwijderd]

Op vrijdag 19 april 2002 00:29 schreef Yarvieh het volgende:
tip pascal kent wel shl en shr volgens mij?

Voor bitwise operations is shift left en shift right idd. de juiste oplossing:

code:

0001 shl 1=0010 (2)
0010 shl 1=0100 (4)
0001 shl 3=1000 (8)

1101 shr 1=0110 (6)

In Delphi heb ik even wat geprobeerd, misschien moet het in Turbo Pascal iets anders maar het gaat om het idee.

code:

type
  TBitArray=array[1..32] of Boolean;

function DWORDToBits(const Value: DWORD): TBitArray;
var
  I: DWORD;
begin
  for I:=High(Result) downto Low(Result) do
    Result[I]:=(Value and (1 shl (High(Result)-I)))<>0;
end;

function BitsToDWORD(const Value: TBitArray): DWORD;
var
  I: DWORD;
begin
  Result:=0;
  for I:=High(Value) downto Low(Result) do
    Result:=(Result or (DWORD(Value[I]) shl (High(Value)-I)));
end;

[Janoz]

Op vrijdag 19 april 2002 01:23 schreef Soultaker het volgende:

Bij deze dus een leuker vraagstuk: bedenk een algoritme met een lagere complexiteit maar dezelfde werking.

Iedereen begint gelijk met shifts... Maar dat is natuurlijk niet de bedoeling.. Dat werkt alleen bij machten van 2

Hier een algoritme dat niet O(n) maar O(log n) is (met n als exponent)

psuedo voor aⁿ n is een integer en deling is een gehele deling die naar beneden afrond.

code:

functie pow(a,n) {
  if n==1 {
    return a;
  } else {
    b=pow(a,n/2);
    if even(n) {
    return b*b;
    } else {
    return b*b*a;
    }
  }
}

_{typefouten voorbehouden}

of mocht ik niet meedoen Soultaker

[RickN]

Op vrijdag 19 april 2002 11:10 schreef Janoz een erg lelijke implementatie van een erg bekend algoritme:

Ik had beter van jouw verwacht Janoz, NOFI.

(Recursie? Voor een simpele machtsverheffing??? PE-LEASE!)

[Verwijderd]

Op vrijdag 19 april 2002 11:10 schreef Janoz het volgende:

[..]

Iedereen begint gelijk met shifts... Maar dat is natuurlijk niet de bedoeling.. Dat werkt alleen bij machten van 2
[...]

Het ging over omzetting van binair-decimaal, dus heb je alleen machten van 2 nodig.

[Janoz]

Op vrijdag 19 april 2002 11:18 schreef RickN het volgende:

[..]



Ik had beter van jouw verwacht Janoz, NOFI.

(Recursie? Voor een simpele machtsverheffing??? PE-LEASE!)

Ach, ik heb 'm in 5 sec neergeplant, en hij is efficienter dan de eerste genoemde , en ik was geinspireerd door het fibonatchi topic...

Verder ga ik in op de vraag van Soultaker en niet van de topicstarter.. Vandaar dat deze ook met andere grondtallen werkt

[henkleerssen]

mmm.. basiswiskunde geloof ik...Janoz? ..euh ik kan me vergissen (pascal lessen een tijd gelee gehad)... maar is de operator "^^" niet wat je zoekt? dus 2 tot de macht 5 wordt 2^^5 (ik heb ff geen pascal compiler om te testen).

[Soultaker]

Janoz heeft 't goed begrepen. Wel jammer van de recursie. Een logische vervolgvraag zou dus zijn: maak een iteratieve versie.

Een wiskundig bewijs of tenminste enige uitleg zou natuurlijk ook leuk zijn, misschien leert er dan iemand nog wat van deze topic.

[RickN]

Op vrijdag 19 april 2002 15:53 schreef Soultaker het volgende:
[..]
Een wiskundig bewijs of tenminste enige uitleg zou natuurlijk ook leuk zijn, misschien leert er dan iemand nog wat van deze topic.

U vraagt wij draaien:

Introduceer een functie G met:

G.x.y = x^y

Nu geldt:
G.x.0
={wiskunde}
1

G.x.y /\ y mod 2 = 0
={definitie G}
x^y /\ y mod 2 = 0
={wiskunde}
x^{2(y div 2)}
={wiskunde}
(x²)^{y div 2}
={definitie G}
G.x².(y div 2)

G.x.y /\ y mod 2 = 1
={definitie G}
x^y /\ y mod 2 = 1
={wiskunde}
x^1+y-1
={wiskunde}
x¹ * x^y-1
={wiskunde}
x * x^y-1
={definitie G}
x * G.x.y-1

Een staart invariant voor G:
P0: r * G.x.y = G.A.B

Met de recurente betrekking voor G vinden we:
P0 /\ y>0 /\ y mod 2 = 0 => P0(x,y:=x²,y div 2)
en
P0 /\ y>0 /\ y mod 2 = 1 => P0(r,x:=r*x,y-1)

Dit alles resulteerd in:

code:

|[var x,y: int {A, B >= 0}
   r, x, y := 1, A, B;
   {P0 /\ y>=0}
   do y <> 0
    -> if y mod 2 = 0 -> x, y := x*x, y div 2
       [] y mod 2 = 1 -> r, y := r*x, y-1
       fi
   od
   {P0 /\ y=0 dus r = A^B
]|
{r = A^B}

[Soultaker]

Op vrijdag 19 april 2002 17:26 schreef RickN het volgende:
U vraagt wij draaien:

ZO ingewikkeld had ik 't zelf niet kunnen opschrijven. (En wat een creatieve /\ symbolen.)

Dit alles resulteerd in:

code:

|[var x,y: int {A, B >= 0}
   r, x, y := 1, A, B;
   {P0 /\ y>=0}
   do y <> 0
    -> if y mod 2 = 0 -> x, y := x*x, y div 2
       [] y mod 2 = 1 -> r, y := r*x, y-1
       fi
   od
   {r*x^y = A^B /\ y=0 dus r = A^B
[|
{r = A^B}

Moet dat pseudocode voorstellen? Of is dit een bestaande vage programmeertaal (en welke dan wel)?

[Verwijderd]

Lang leve GCL

[Verwijderd]

sqr

[RickN]

Op vrijdag 19 april 2002 17:34 schreef Soultaker het volgende:

[..]

ZO ingewikkeld had ik 't zelf niet kunnen opschrijven. (En wat een creatieve /\ symbolen.)
[..]

Mwa, niet zo ingewikkeld hoor, tis ff wennen.

Moet dat pseudocode voorstellen? Of is dit een bestaande vage programmeertaal (en welke dan wel)?

GCL dus, Guarded Command Language. Niet compileerbaar ofzo, maar wel met een zeer duidelijk vastgelegde semantiek.

[Verwijderd]

Ooit uit verveling gemaakt en ik weet dat het 1000 maal makkelijker kan maar toen was ik nog een pascal n00b...

code:

program binairgelul (input, output);

const
   MAX = 30;

type
   tabeltype = array[1..MAX] of integer;

var
   som     : integer;
   kar     : integer;

Procedure getaltobinair;

var
   getal   : integer;
   teller  : integer;
   teller2 : integer;
   temp    : integer;
   bigetal : boolean;
   nummer  : char;

begin
   write ('Geef een getal: ');
   read (nummer);
   getal := ord(nummer) - ord('0');
   writeln;
   bigetal := false;
   write ('Het getal ', getal,' is in binaire getallen dit: ');
   for teller := 1 to MAX do
   begin
    temp := 1;
    for teller2 := 1 to (MAX - teller) do
        temp := temp * 2;

    if getal div temp = 1 then
    begin
       write ('1');
       getal := getal mod temp;
       bigetal := true;
    end
    else
    begin
       if bigetal = true then
        write ('0');
       getal := getal mod temp;
    end
   end;
   writeln;
   readln;
end;


procedure binairtogetal  (var psom : integer);

var
   tabel   : tabeltype;
   nummer  : char;
   n     : integer;
   teller  : integer;
   teller2 : integer;
   temp    : integer;

begin
   writeln ('geef nu een binaire code tussen elk getal een spatie');
   n := 0;
   while not eoln and (n < MAX) do
   begin
    read(nummer);
    n := n + 1;
    tabel[n] := ord(nummer) - ord('0');
   end;
   for teller := 1 to n do
   begin
    temp := 1;
    for teller2 := 1 to (n - teller) do
        temp := temp * 2;
    if tabel[teller] = 1 then
       psom := psom + temp
   end;
   writeln;
   writeln('Het decimale getal is: ',psom)
end;

begin {hoofdprogramma}
   writeln ('maak een keuze uit de volgende mogenlijkheden: ');
   writeln;
   writeln ('1. Binair to Decimaal.');
   writeln ('2. Decimaal to Binair.');
   writeln;
   write ('Geef nu je keuze... ');
   readln(kar);
   som := 0;
   if kar = 1 then
    getaltobinair ;
    if kar = 2 then
      binairtogetal (som)
    else
      writeln ('Er is een ongeldige waarde ingevoerd.')
end.

[Skinkie]

Op vrijdag 19 april 2002 00:58 schreef Ublis het volgende:
A^B = exp(A*ln()

Beter opletten bij wiskunde .

wat bedoel je nou met exp?

[Verwijderd]

Op vrijdag 19 april 2002 19:52 schreef RickN het volgende:

GCL dus, Guarded Command Language. Niet compileerbaar ofzo, maar wel met een zeer duidelijk vastgelegde semantiek.

Een TU/e student, herken je onmiddellijk... Kan me de eerste jaars colleges Prog.1 van Hoogerwoord nog wel herinneren.

[RickN]

Op zaterdag 20 april 2002 00:33 schreef Hieronymus het volgende:

[..]

Een TU/e student, herken je onmiddellijk... Kan me de eerste jaars colleges Prog.1 van Hoogerwoord nog wel herinneren.

Dat was echt genieten, net als alle vakken die erop voortborduurde. Hoogerwoord is GE-WEL-DIG.

En ik meen het ook nog.

[Verwijderd]

Dan vind je Feijen en v. Gasteren vast ook geweldig (De Dijkstra-kloontjes )
Nog een half jaartje, en dan mag ik hopelijk afstuderen...

[Exirion]

Op zaterdag 20 april 2002 00:33 schreef Hieronymus het volgende:
Een TU/e student, herken je onmiddellijk...

Pure theoretici ja Een collega van me komt ook van de TUE en beaamt het zelf Hij kan het ook moeilijk ontkennen met de zeer matige technische- en praktijkervaring die hij heeft

[Verwijderd]

Op zaterdag 20 april 2002 01:31 schreef Exirion het volgende:

Pure theoretici ja Een collega van me komt ook van de TUE en beaamt het zelf Hij kan het ook moeilijk ontkennen met de zeer matige technische- en praktijkervaring die hij heeft

Daar hebben we toch HBO studenten voor Althans dat vertellen ze je altijd op de TU/e

[Bergen]

Op zaterdag 20 april 2002 01:33 schreef Hieronymus het volgende:

[..]

Daar hebben we toch HBO studenten voor Althans dat vertellen ze je altijd op de TU/e

Dat klinkt net of het 'voorwerk' wat TU-ers doen superkewl is en 't programmeren 't saaie nawerk is! Maar 't programmeren is toch juist veel leuker werk?

[tomato]

Hieronymus: Daar hebben we toch HBO studenten voor Althans dat vertellen ze je altijd op de TU/e

Op de TU/e kunnen ze je nog meer vertellen, maar het is wel een technische universiteit

[Verwijderd]

Op zaterdag 20 april 2002 02:38 schreef GerbenW het volgende:
Dat klinkt net of het 'voorwerk' wat TU-ers doen superkewl is en 't programmeren 't saaie nawerk is! Maar 't programmeren is toch juist veel leuker werk?

Valt wel mee hoor, echt superkewl is het neit, maar zeker wel nuttig om te hebben gehad Ik zit ook liever in C++ te schrijven dan in GCL

[NightBird]

Op zaterdag 20 april 2002 00:09 schreef Skinkie het volgende:

[..]

wat bedoel je nou met exp?

de e-macht.

[RickN]

Op zaterdag 20 april 2002 01:28 schreef Hieronymus het volgende:
Dan vind je Feijen en v. Gasteren vast ook geweldig (De Dijkstra-kloontjes )
Nog een half jaartje, en dan mag ik hopelijk afstuderen...

Uiteraard zijn Feijen en van Gasteren ook geweldig. Heb je hun nieuwe boek al gelezen? "On a method of multiprogramming" HEEEEEEEEERLIJK.
BTW, wat specialiseer je?

Op zaterdag 20 april 2002 01:31 schreef Exirion het volgende:

[..]

Pure theoretici ja Een collega van me komt ook van de TUE en beaamt het zelf Hij kan het ook moeilijk ontkennen met de zeer matige technische- en praktijkervaring die hij heeft

Daar ben ik het absoluut niet mee eens. Relatief weinig praktijk ervaring ja, maar dat heb je op elke universiteit. En technische kennis...praat je dan over programmeer taaltjes leren? Dat is toch volkomen irrelevant, als je kunt programmeren kun je het in elke taal, het is dan nog gewoon een kwestie van de syntax leren. Ze gaan op de TU/e soms wat te ver met theorie (ie berekeningsmodellen en processalgebra voor de kenners) maar al met al ga je niet naar de universiteit voor een Java cursus. In 4 jaar TU/e heb ik geen enkele cursus in een specifieke programmeertaal gehad, hooguit een sprinkeltje pascal. Ik zou het niet anders hebben gewild. Door opdrachten en wat bijbaantjes spreek ik nu een aardig woordje Delphi en C++, daarnaast heb ik geroken aan MPI, Java en Haskell. SQL spreek ik beter dan de meeste mensen hier en ik dank de goden nog elke dag dat ik niet ben vervuilt met zaken als VB, Perl, HTML, PHP, ASP and what have you. Mijn abstractie vermogen is wel goed ontwikkeld en met mijn algoritmische kennis zit het helemaal wel goed. Kortom, smaken verschillen natuurlijk, maar ik ben tevreden over de TU/e, als had het best wat moeilijker mogen zijn.

[edit]Mag ik overigens vragen waar je zelf studeert? Uit je profiel leid ik af dat je in Amsterdam studeert. Daar heb ik nou op en aanmerkingen op.... Ik snap niet waarom iemand in godsnaam een technische studie op een niet technische universiteit gaat doen?

[Verwijderd]

Op zaterdag 20 april 2002 10:48 schreef RickN het volgende:

Uiteraard zijn Feijen en van Gasteren ook geweldig. Heb je hun nieuwe boek al gelezen? "On a method of multiprogramming" HEEEEEEEEERLIJK.
BTW, wat specialiseer je?

..

Ze gaan op de TU/e soms wat te ver met theorie (ie berekeningsmodellen en processalgebra voor de kenners)

Specialisatie voor mij wordt Informatie Systemen.
Het nieuwe boek van F&vG heb ik niet gelezen nee, hoorde er toevallig wel over in de wandelgangen.
Het nadeel van Feijen colleges vind ik wel dat die man echt hamert op het bewijs, tuurlijk is een bewijs belangrijk, maar er is nog meer dan alleen een bewijs aan een goed programma.

Tegenwoordig proberen ze wel wat aan de theoriciteit te doen. Zie ook de OGO-projecten en Software Engineering. OOk krijgen we dus gleukkig meer talen dan alleen een snufje pascal, nu zelfs C++ bij B. Watson!

[RickN]

Op zaterdag 20 april 2002 12:18 schreef Hieronymus het volgende:

[..]

Specialisatie voor mij wordt Informatie Systemen.
Het nieuwe boek van F&vG heb ik niet gelezen nee, hoorde er toevallig wel over in de wandelgangen.
Het nadeel van Feijen colleges vind ik wel dat die man echt hamert op het bewijs, tuurlijk is een bewijs belangrijk, maar er is nog meer dan alleen een bewijs aan een goed programma.

Ja, maar hij kan wel goed uitleggen. Hij heeft wel wat tegen 1ste en 2de jaars trouwens, dat kun je goed merken. Wat ook wel cool aan em is is die achtelijke lepel die ie altijd om z'n nek heeft hangen en dat ie altijd zo een beetje van voor naar achter aan het wiegen is als ie staat na te denken

Tegenwoordig proberen ze wel wat aan de theoriciteit te doen. Zie ook de OGO-projecten en Software Engineering. OOk krijgen we dus gleukkig meer talen dan alleen een snufje pascal, nu zelfs C++ bij B. Watson!

OGO was er nog niet toen ik bezig was. Wel het software engineering project, en ik moet toegeven, dat was één van de leukste dingen die ik heb gedaan op de TU/e.

[Verwijderd]

Op zaterdag 20 april 2002 00:09 schreef Skinkie het volgende:

[..]

wat bedoel je nou met exp?

"Exp returns the value of e raised to the power of X, where e is the base of the natural logarithms." [Delphi documentatie]

[Tomatoman]

Op vrijdag 19 april 2002 00:58 schreef Ublis het volgende:
A^B = exp(A*ln()

Beter opletten bij wiskunde .

Het moet natuurlijk zijn:

A^B = exp(B*ln(A))

maar het idee klopt verder helemaal. Ublish geeft hier de standaardoplossing waar elke Pascal-docent blij van gaat kijken . In Pascal-code:

code:

uses Math;

function Macht(Basis, Exponent: Double): Double;
begin
  Macht := Exp(Exponent * Ln(Basis));
end;

Het leuke van deze functie is dat 'ie ook met niet-gehele machten werkt.