Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: Moneo on June 23, 2003, 10:32:28 PM



Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 23, 2003, 10:32:28 PM
Code:

Ok, here's the rules:

1) It must be considered an algorithm, formula or method.
    Add 15 to X   ----   X=X+15    This is not an algorithm, agreed?
    If it were, then every line of code in a program would be.

2) You must describe the algorithm first, i.e., what is its purpose.

3) Then show the one line of code.

4) Multiple statments on one line; like: x=x+1 : x=x and 15
    are not considered as one line of code.

A good example is one we've already seen with the XOR.
The purpose is to turn a switch on if it's off, and turn it off if it's on.
The one line of code is: sw=sw xor sw
or equally cool:              sw=1-sw

*****


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on June 23, 2003, 11:17:04 PM
The cycling counter:

Code:
counter% = (counter% + 1) MOD max%


If max% is a power of two it is better to do...

Code:
counter% = (counter% + 1) AND (max% - 1)


Does this one count? :)


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 24, 2003, 01:28:37 AM
Yes nathan, it may count if I can figure out what you mean by a "cycling counter".  Does your one instruction finish the whole idea?
*****
EDIT:
I just figured out with pencil and paper what you want to do. It's brilliant!
You want to do (or cycle) some code max number of times, where max is a power of 2. Actually, because of the logic, you need to do this from zero to max-1.
You need the following setup or initialization.

max = (some power of 2) - 1
counter = 0
gosub logic

Then, your one line algorittm embedded in a loop becomes:

loop:
counter = (counter + 1) and max
gosub logic
goto loop

In this manner, your one line instruction to increment and reset will enable us to perform the subroutine called "logic" repeatedly for values of zero to max.
The rest of you should notice the subtle point of his instruction, in that when the counter is incremented 1 beyond max, the "and" wraps it around to zero.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: seph on June 24, 2003, 02:06:38 AM
I've tried the code and basically it counts starting at counter% until it hits max%, at which point it sets counter% to 0. Basically a normal counter. Works best in DO ... LOOPs. Might be used for a delay method.


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on June 24, 2003, 02:06:47 AM
Here's mine, to turn a switch on if off, or off if on, without using XOR. x = 1 if on, and 0 if off.

Code:
x = ((x = 0) AND 1) OR (1 AND (X = 0))


Though I suspect there may be an easier way, the logical (x=0) may be a hint to others about other algos.

EDIT: Aah. I've just seen Moneo's other way in the XOR thread. But my way still works.


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 24, 2003, 02:33:12 AM
Oracle,
I didn't complie and check yours out, but it looks like you're trying to implement an XOR without using it, which would be like:
a=a XOR b
is the same as
a=(a and not(b)) or (b and not(a))

So, let's substitute your x for a in the above, and 1 for b in above.
So then we have what I think you wanted:
x=(x and (not(1)) or (1 and not(x))

That looks awful. It's late here, let me compile and test it tomorrow.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Agamemnus on June 24, 2003, 10:43:11 AM
Is this good? :|

Code:

CLS
fact& = 12
fact2& = 1

1 IF fact& = 2 THEN fact2& = fact2& * 2 ELSE fact2& = fact2& * fact&: fact& = fact& - 1: GOTO 1

PRINT fact2&


Title: To Oracle: 2nd look at your code.
Post by: Moneo on June 24, 2003, 01:07:16 PM
Quote from: "oracle"
Here's mine, to turn a switch on if off, or off if on, without using XOR. x = 1 if on, and 0 if off.

Code:
x = ((x = 0) AND 1) OR (1 AND (X = 0))



I was wrong. You are not implementing an XOR. Your code above is a very good approach and it works.

However,  the second expression after the OR is exactly the same as the first expression, and therefore you can just exclude it, leaving the resultant code as:
Code:
x = ((x = 0) AND 1)


Another observation: You have introduced the fact that any expression, like (x=0), results in a true (-1) or false (0) condition. For example:
result = (a>b)
if a is greater than b, result is -1, true
if a is not greater than b, then result is 0, false.

You did great, Oracle!
*****


Title: To Seph and Agamemnus:
Post by: Moneo on June 24, 2003, 01:17:36 PM
Quote from: "seph"
I've tried the code and basically it counts starting at counter% until it hits max%, at which point it sets counter% to 0. Basically a normal counter. Works best in DO ... LOOPs. Might be used for a delay method.


Good observations, Seph.

Another use of this "increment and auto wrap at max" logic could be when you are processing a circular buffer whose size is a power of 2. Every time you access the buffer, you don't need to ask "I am at the end of the buffer?" and waste the execution time to test it.
*****
TO AGAMEMNUS:
It might be good if you gave us a hint as to what you want to do. Also, the clause after the ELSE has 2 instructions on it, which are not allowed.
*****


Title: factorial.
Post by: Agamemnus on June 24, 2003, 01:51:12 PM
d'oh! It's factorial!! Well, I have no idea how to code it otherwise. :|


Title: To Agamemnus
Post by: Moneo on June 24, 2003, 02:21:45 PM
Oh, you want to compute the factorial of a number. Well, for the moment, I can't see how you can do that in one line of code, without a function of course. Normally a factorial is computed using a FOR loop. That doesn't mean that it can't be done.  Keep trying.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 25, 2003, 02:43:24 PM
Here's a little algorithm that I derived.

Given a positive integer number N, compute the next multiple of X:
Result to M.

   defint a-z

   M = int((N+X)/X)*X

Note: "next" multiple means that if you're already at a multiple, you move up to the next multiple. Example: if N=5 and X=5, the result will be 10.

If you got that, then make a slight change to the algorithm to compute the "nearest" multiple. Example: if n=5 and x=5, the result is 5 because it is the nearest (you're already there). This is like rounding --- if it's already rounded, then that's the answer.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on June 25, 2003, 03:30:31 PM
Factorial in one line?
Code:

function fact&(x&):if x& then fact&=x&*fact&(x&-1) else fact&=1 :end function


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 25, 2003, 04:16:37 PM
Wow, Antoni! A recursive call to itself --- very sofisticated!
Let me try it out .
*****
Scolta noi ------------- it works!
Brilliant, Antoni.

*****


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on June 25, 2003, 06:12:32 PM
I have not tested it, but I think it does'nt work.
END FUNCTION can't be in the same line of a single line IF...


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 25, 2003, 06:33:46 PM
Antoni, What I tested was the your one line of code in between a standard Function definition line and a standard End Function line.
It's still a one line function.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on June 25, 2003, 06:55:40 PM
Thanks for considering it like this!


Title: Challenge: Algorithms having only one line of code.
Post by: Agamemnus on June 25, 2003, 10:15:07 PM
HEY! NO FAIR!

IT's THREE LINES OF CODE!


Title: Challenge: Algorithms having only one line of code.
Post by: seph on June 26, 2003, 01:57:29 AM
I don't understand what that function does or what a factoral is. Please explain EVERYTHING IN THE UNIVERSE to me.

Nevermind. Some jerk named dictionary.com very rudely explained it to me...


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on June 26, 2003, 09:59:52 AM
Well, in the line of Antoni's, here's my very own fibonnaci series callculator:

Code:
FUNCTION fibonacci& (n&)
   IF n& < 2 THEN fibonacci& = 1 ELSE fibonacci& = fibonacci&(n& - 1) + fibonacci&(n& - 2)
END FUNCTION


You use it this way (for example):

Code:
FOR i& = 0 TO 10
   PRINT fibonacci(i&)
NEXT


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 26, 2003, 01:06:03 PM
Quote from: "Agamemnus"
HEY! NO FAIR!

IT's THREE LINES OF CODE!


Technically, you're right, but Antoni's approach still merits recognition within the constraints of this challange.

Your approach also deserves merit for its simplicity, even though it needs the extra GOTO instruction to work.
I recommend making it a little shorter as follows:
Code:

REM 1 IF fact& = 2 THEN fact2& = fact2& * 2 ELSE fact2& = fact2& * fact&: fact& = fact& - 1: GOTO 1

1 IF fact& > 1 THEN fact2& = fact2& * fact&: fact& = fact& - 1: GOTO 1

*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 26, 2003, 03:57:43 PM
Quote from: "na_th_an"
Well, in the line of Antoni's, here's my very own fibonnaci series callculator:
Code:
FUNCTION fibonacci& (n&)
   IF n& < 2 THEN fibonacci& = 1 ELSE fibonacci& = fibonacci&(n& - 1) + fibonacci&(n& - 2)
END FUNCTION

Excellent na-th-an! Here again we have a brilliant recursive function.
 
How many of you know what a Fibonacci series is? It's a series where any number in the series is the sum of the two preceding numbers., i.e., 1,1,2,3,5,8,13 .....

What would you use a Fibonacci series for? What is a practical use?
*****


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on June 26, 2003, 04:53:30 PM
Well, it is very used to teach recursion and algorithmics, but it came from a simple problem:

Fibonacci wanted to determine the rate at which pairs of rabbits would reproduce.

Info here : http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html#Rabbits


Title: To na_th_an:
Post by: Moneo on June 26, 2003, 07:15:44 PM
I agree that Fibonacci first developed his famous series to see the reproduction rate of rabbits.

But, what would I use this series for today in computer programming applications?

I personally have only seen one practical use of the series, and that was for a polyphase merge sort used on an IBM mainframe with only 3 tape drives available. The Fibonacci series determined how many internally sorted "runs" were distributed onto each of the tapes, so that only one of the 3 tapes (the one with the least number of runs) had to be rewound at the end of a given sort pass.

Polyphase merge sorts have become a popular academic topic. Many implementations using more than 3 tapes still continue to use the Fibonacci series. It works, although studies have shown that this series is not the most efficient for over 3 tapes.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on June 27, 2003, 04:57:34 AM
I use the fibonacci series to test StatLib. Though that may not be useful in real life...

StatLib nearly has negative and decimal support! (sorry, spamming...)

The factorial method came up in my other challenge, the statistical one that started statlib off, that's why so many people have been repoducing it. I think only na_th_an should get the recognition for it, because he won.


Title: Challenge: Algorithms having only one line of code.
Post by: LooseCaboose on June 27, 2003, 05:55:16 AM
Basic is kinda hopeless for this task for all but the very simplest algorithms because even a loop construct requires more than one line:
Code:

while condition : wend

Futhermore you cant make assignments within the condition part of a loop because Basic interprets this as a test for equality.

So, seeing as your rules didn't actually specify that I have to write Basic code, heres a pseudo bubble sort in one line of Java or C++ code (Wont work in C because you arent allow to declare variables within the expression list of a for loop:
Code:

for(int a[5]={2,4,3,5,1},int t,int i=0;i<4;i++){if(a[i]<a[i+1]){(t=a[i])&&(a[i]=a[i+1])&&(a[i+1]=t)&&(i=-1);}}

Sorts the array a in descending order. It differs from most bubble sort implementations becuase it only uses a single loop (by resetting i every time it does a swap). On the plus side, in the best case (data is already sorted) the algorithm works in linear O(n) time, however in the worst case it runs in O(n ^ 2).


Title: ok,
Post by: Agamemnus on June 27, 2003, 09:17:07 AM
now make a one-line quicksort algorithm that sorts two linked arrays. (eg. "Joe", 90, "Aga", 89.9999, "Wildcard", 101.1

 :o


Title: To Oracle re Statlib
Post by: Moneo on June 27, 2003, 02:39:42 PM
What is Statlib?
*****


Title: Re: To na_th_an:
Post by: na_th_an on June 27, 2003, 05:14:21 PM
Quote from: "Moneo"
But, what would I use this series for today in computer programming applications?


This one is for Moneo. Sorry, it is in spanish. I took this off a web:

Quote
La serie de Fibonacci

Esta serie fue descubierta por un matemático italiano del siglo XIII, llamado Fibonacci. Cada número de la serie es el resultado de la suma de los dos anteriores. Veamos que aspecto tiene:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

 Esta serie posee propiedades muy interesantes entre las cuales vamos a destacar la relación existente entre los números que la componen:
si dividimos los números que son consecutivos de la serie, es decir, 1/1, ½, 2/3, 3/5, 5/8, 8/13, etc. veremos que el resultado obtenido tiende al número 0.618.

 si dividimos los números no consecutivos de la serie, es decir, ½, 1/3, 2/5, 3/8, 5/13, 8/21, etc. veremos que el resultado obtenido tiende al número 0.382.

 si calculamos ahora la razón de cualquier número de la serie al siguiente número más bajo, es decir, 21/13, 13/8, 8/5 ... el resultado tiende a 1.618, que es el inverso de 0.618.

 si calculamos ahora la razón de cualquier número de la serie al siguiente número más bajo no consecutivo, es decir, 21/8, 13/5, 8/3 ... el resultado tiende a 2.618, que es el inverso de 0.382.

De este modo hemos obtenido un conjunto de ratios que ya eran conocidos y utilizados con anterioridad a Fibonacci por los antiguos griegos y egipcios. Conceptos derivados de estos ratios como la proporción áurea fueron aplicadas en construcciones como la pirámide de Gizeh o el Partenón. Nosotros vamos a mostrar como estos ratios van a tener aplicación directa como herramientas de análisis a la hora de determinar porcentajes de corrección contra la tendencia principal. ¿Dónde está el punto de unión de lo expuesto en esta primera parte y el mercado de valores? La explicación que podemos ofrecer a priori resulta un poco esotérica pero confiamos en que los lectores, con el tiempo, y el uso de esta técnica, constaten de modo empírico su utilidad. Mientras tanto, la idea que subyace tras esta serie es que la espiral logarítmica que puede construirse en base a ella, describe parte de la figura de crecimiento que se puede apreciar en todo el Universo. Ejemplos de manifestación de esta espiral se ven en las conchas, el caparazón del caracol, la forma de la galaxia, el oído humano. Por tanto, se cree que el mercado de valores, además de representar un ejemplo del comportamiento de la masa humana, es una manifestación del fenómeno de crecimiento natural que caracteriza todo progreso humano.


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 27, 2003, 06:30:28 PM
Thanks, na_th_an,
There is a vast amount of information published regarding the Fibonacci series, but mostly scientific. Only a few very elite computer programmers are afforded the opportunity to participate in such scientific projects. So, aside from the polyphase merge which I already mentioned, I would like to know of other "practical" applications.
*****


Title: To LooseCaboose:
Post by: Moneo on June 27, 2003, 07:08:32 PM
Sorry, LooseCaboose, but this challenge is for Basic programs exclusively. Otherwise we would need every compiler in the universe to check out submitted code entries.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: LooseCaboose on June 27, 2003, 09:45:32 PM
Quote

Sorry, LooseCaboose, but this challenge is for Basic programs exclusively.


Oh well, I was just being pedantic because your rules don't state what langauge I have to write in. I have tested the code an it does work.

Like I said, its really hard to write one line algorithms in basic because all of the constructs (if, while, select, etc) require more than one line. Na_th_an's modulo counter was cool and Oracle's bit flip thing was neat, but as I said before the following works almost as well for flipping between an on and off state:
Code:

x = NOT x

The advantage of Oracle's approach is that any non-zero value will be flipped to zero, whereas my example flips between x and -x only.

Antoni's and Na_th_an's recursive functions are very clever, but don't actually obey your rules because they both use either the colon line separator or three lines with a proper function body, however seeing as you are accepting them heres one which calculates the sum of the values 1 to n:
Code:

function sum%(n as integer)
  if n = 1 then sum% = 1 else sum% = n + sum%(n - 1)
end function


Title: Re: To Oracle re Statlib
Post by: oracle on June 27, 2003, 09:50:16 PM
Quote from: "Moneo"
What is Statlib?
*****


StatLib was born out of the statistical challenge mentioned before (which na_th_an won), and also out of a wonderful idea by Neo (who is away on holiday at the moment). Basically put, it is a library used for calculating many complicated statistical functions, like factorials, binomial theorem, array sorting and graph drawing, but the difference is Neo's idea, which stores all numbers as strings instead of the typical data types, making calculation of numbers like 2000! and the 3000th fibonacci number a snap in QBasic.

Unfortunately I'm very busy at the mo so I'm ignoring it most of the time, but if I had a spare day or two the engine would be done and then only the actual statistical functions would be left.


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 27, 2003, 11:04:29 PM
Quote from: "LooseCaboose"

..... but as I said before the following works almost as well for flipping between an on and off state:
Code:

x = NOT x

Yery good, LooseCaboose. Believe it or not, your aproach is probably the most commonly used. Most programmers consider TRUE as -1, and FALSE as 0. In that manner they can say: if x then .... when they're testing for true. But you have to be careful because the if x then .... will consider x as true for ANY NON-ZERO VALUE.

In order for your fliipflop to work right, you must start out with x equal to 0 or -1, use your code to flip it, and only reset it, if needed, to 0 or -1.

To make the code more understandable, I usually do:
Code:

defint a-z

const false = 0
const true  = not(false)

switch = false   'asumming we want to start off as false
.....
if switch = false then ..... 'to test false
.....
if switch = true then .....  'to test true
.....
switch = not switch         'to flip it (your way)
.....
switch = true                   'to unconditionally set to true at any time

*****


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on June 28, 2003, 01:12:55 AM
To do a bullet proof flip-flop in QB where -1 is TRUE and 0 is FALSE (for convention, as -1 has all bits set)...

Code:
x% = NOT -ABS(SGN(x%))


That way, if x%<>0 -> it will turn 0 (FALSE), and if x%=0 it will turn -1 (TRUE).

I know that any nonzero value is equal to an IF, but if you are gonna do bitwise operations later you'll have problems if that number isn't -1 (all bits set).


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on June 28, 2003, 03:07:21 AM
Aah.. I've been looking for something like that...

Ye olde random number generator function... very old this...

Code:
DEF FNran (x) = INT(RND(1) * x) + 1


Calculate pi exactly

Code:
pi# = 4 * ATN(1)


Both pretty useless, but there they are...


Title: To Oracle:
Post by: Moneo on June 28, 2003, 07:10:09 PM
Your one liner to generate PI is pretty slick. I never saw that before. I checked your reslult against a calculator program, and it matches exactly to 15 decimal places. Excellent!

Regarding the random number generator, I'll have to assume it works 'cause it's very hard to check out; that is, how truly random is a random number?
*****


Title: Challenge: Algorithms having only one line of code.
Post by: ak00ma on June 29, 2003, 06:29:06 AM
There's another pi-generator formula, MariuZ and I made, but if you do it in QB, you will have to code a new Sinus function, because the formula uses angles expressed in degrees and not in radians:

Code:

Pi = n * Sin(180°/n)


n is the number of edges of a polygon...the higher n is, the exacter Pi will be generated....


Title: Challenge: Algorithms having only one line of code.
Post by: Ninkazu on June 29, 2003, 03:02:53 PM
That doesn't work at all...


Title: Challenge: Algorithms having only one line of code.
Post by: ak00ma on June 29, 2003, 04:53:24 PM
you can't use the Sin function of QB, I said this...you must take a sin function that uses degrees and not radians...try it


Title: Challenge: Algorithms having only one line of code.
Post by: DrV on June 29, 2003, 05:01:56 PM
to have a sine that uses degrees, you must convert the degrees to radians at some point if you wish to use the internal SIN function, and to do this, you need to know the value of Pi...


Title: To Ak00ma:
Post by: Moneo on June 29, 2003, 07:39:36 PM
I took out the degrees sign (º), and tried it in QuickBasic, like so:
Pi = n * Sin(180/n)

Pi is defined as double, and n as integer.

Using n=4, it gives an answer of 3.4036-----
Using n=256, it gives.............. 165.5307-----

Something is not right.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: DrV on June 29, 2003, 08:07:14 PM
See ak00ma's post above... you must use a sine function that takes degrees as an argument, and you can't really write one without either making a lookup table, or using the builtin SIN function, using PI so you can convert degrees to radians...  so whip out your old algebra book and start typing...


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on June 29, 2003, 08:53:35 PM
That's the trouble isn't it... to convert from degrees to radians you have to have pi, and you are trying to calculate pi anyway, so how can you get the answer anyway, when the answer is part of the question?

Also, the random function is not really random, we had this discussion a little while ago somewhere (me, Hex, Glenn, Aga), all the random function does is go through 16 million numbers and repeat. RANDOMIZE TIMER just chooses a different starting point...


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on June 29, 2003, 11:35:40 PM
Ok, let's get back to the topic. We haven't had a one-line algorithm since Oracle's calculation for PI.

A few days ago I posted the following:
Code:
Given a positive integer number N, compute the next multiple of X:
Result to M.

defint a-z

M = int((N+X)/X)*X

Note: "next" multiple means that if you're already at a multiple, you move up to the next multiple. Example: if N=5 and X=5, the result will be 10.

If you got that, then make a slight change to the algorithm to compute the "nearest" multiple. Example: if n=5 and x=5, the result is 5 because it is the nearest (you're already there). This is like rounding --- if it's already rounded, then that's the answer.

Nobody came up with the method of computing the "nearest" multiple, so here it is:
Code:

   M = int((N+X-1)/X)*X

*****


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on June 30, 2003, 01:42:24 AM
I already made a function to do that for statlib... pity I'll have to rewrite it because I'm using strings now...

Functions for finding roots of quadratic equations. Two needed: one for each root.

Code:
a = 1
b = 4
c = 2
' equivilant to x²+4x+2

r1 = (-b + (SQR(b ^ 2 - (4 * a * c)))) / (2 * a)
r2 = (-b - (SQR(b ^ 2 - (4 * a * c)))) / (2 * a)
PRINT r1, r2
' returns -1, -3


Title: Challenge: Algorithms having only one line of code.
Post by: ak00ma on June 30, 2003, 12:35:55 PM
I only need a sine algorithm that uses degrees and not radians...then I'll code it


Title: Challenge: Algorithms having only one line of code.
Post by: DrV on July 01, 2003, 01:33:50 AM
Quote from: "oracle"
I already made a function to do that for statlib... pity I'll have to rewrite it because I'm using strings now...

Functions for finding roots of quadratic equations. Two needed: one for each root.

Code:
a = 1
b = 4
c = 2
' equivilant to x²+4x+2

r1 = (-b + (SQR(b ^ 2 - (4 * a * c)))) / (2 * a)
r2 = (-b - (SQR(b ^ 2 - (4 * a * c)))) / (2 * a)
PRINT r1, r2
' returns -1, -3

That only finds the real roots... I suppose we'll let you get away with it this time... ;)


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on July 01, 2003, 03:30:54 AM
I know that... *shoots DrV*. How d'you expect me to find complex roots, or even represent them in QB? I suppose it could be done using the symmetrical property of the roots and polar form, but then it wouldn't be one line.


Title: Power of 2
Post by: Moneo on July 01, 2003, 06:42:37 PM
Here's a rather complex one-liner to determine if a given number N is a power of 2.
Code:
defLNG a-z

if 2^(int(log(N)/log(2)+.5)) = N then print n;" is a power of 2"


Note: My original code did not add the .5 to round the result. However, further testing showed that for certain values of N, like 128, the arithmetic failed. Can anyone tell me why 128 fails without the rounding?
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on July 01, 2003, 06:53:41 PM
Adding .5 before INT does round to the next integer, the same as CINT does. INT is a floor function. Maybe your original code is in another language?


Title: To Antoni:
Post by: Moneo on July 01, 2003, 07:03:43 PM
Yes, the original code was in PICKBasic, which is identical for this one line of code.

What do you mean by a "floor function"?

Have you been able to determine why the formula fails for N=128 without the rounding?
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on July 01, 2003, 07:15:53 PM
This way works with 128:
Code:

DEFLNG A-Z
a! = LOG(n) / LOG(2)
IF 2 ^ a! = n THEN PRINT n; " is a power of 2"


So i imagine it's a QB bug...

A floor function rounds towars the smaller integer.


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on July 01, 2003, 07:25:12 PM
I use a replacement for this kind of instruction:

Code:
IF <condition> THEN
   a = <value1>
ELSE
   a = <value2>
END IF


The replacement goes as follows:

Code:
a = (<value1> AND <condition>) + (<value2> AND (NOT <condition>))


Workis well with integer data.


Title: Challenge: Algorithms having only one line of code.
Post by: oracle on July 01, 2003, 11:28:55 PM
I've got a function for statlib somewhere that does correct rounding (eg .5 and up rounds up, and <.5 rounds down) because the QB ones wern't working for all decimal values. I'll try to find it...


Title: Challenge: Algorithms having only one line of code.
Post by: BinarySHOCK on July 02, 2003, 03:10:58 AM
Here's a crappy rounding thingy


N = 3445    ' Number To Round
Dire = 0    ' Direction to round, 1 = Up, 0 = Down

Rounded = CINT(N + ((Dire = 0) - (Dire = 1)) * .5)

PRINT Rounded


Title: 197
Post by: whitetiger0990 on July 02, 2003, 10:29:56 AM
this rounds abd is 1 line of code minus the lines that define the variables.

Code:
dec = 1      'how many decimal places to round
num = 2.56   'number to round
PRINT INT(10 ^ dec * num + .5) / 10 ^ dec

This is actually ALauzier (http://forum.qbasicnews.com/profile.php?mode=viewprofile&u=766)'s but I just posted it


Title: To na_th_an re "replacement" logic:
Post by: Moneo on July 02, 2003, 12:29:09 PM
An excellent example of how a pure logic statement can replace an IF statement.
*****


Title: Re ROUNDING using .5:
Post by: Moneo on July 02, 2003, 12:47:46 PM
Let's not forget that positive numbers are rounded UP using .5, and negative numbers are rounded DOWN using -.5.

So, the simplest way is to test the sign of the number to be rounded, and set the rounding factor to .5 or -.5 accordingly. Something like this:
Code:

IF NUMBER < 0 THEN RFACTOR=-.5 ELSE RFACTOR=.5
RESULT=INT(NUMBER+RFACTOR)

*****


Title: Challenge: Algorithms having only one line of code.
Post by: whitetiger0990 on July 02, 2003, 12:58:28 PM
Code:
CLS
dec = 2
num = -2.7234
IF NUMBER < 0 THEN rfactor = -.5 ELSE rfactor = .5
PRINT INT(10 ^ dec * num + rfactor) / 10 ^ dec

there


Title: Re: Re ROUNDING using .5:
Post by: Moneo on March 19, 2006, 10:19:57 PM
Quote from: "Moneo"
Let's not forget that positive numbers are rounded UP using .5, and negative numbers are rounded DOWN using -.5.

So, the simplest way is to test the sign of the number to be rounded, and set the rounding factor to .5 or -.5 accordingly. Something like this:
Code:

IF NUMBER < 0 THEN RFACTOR=-.5 ELSE RFACTOR=.5
RESULT=INT(NUMBER+RFACTOR)

*****


Hey guys, about a year after posting the above rounding solution, I discovered that using a rounding factor of .5 or -.5 does not work 100% for reasons unknown.

However, during this time, I discovered a foolproof rounding algorithm by Oracle, which is described in detail in this extract from a tutorial I wrote for QBNZ. Sorry I didn't correct this old post sooner. See the one line rounding algorithm at the end.


6. ROUNDING NUMBERS (POSITIVE OR NEGATIVE):
   CREDIT: Oracle of Qbasicnews and QBNZ.
   The purpose is to round positive or negative numbers to the nearest whole
   number. The standard convention of "half-adjusting" by a rounding factor of
   .5 is used. Notice that positive numbers must be rounded up, and negative
   numbers are rounded down, that is, to a greater negative number.

   NOTE: If you do INT(123.9) you will get 123. However, if you do INT(-123.9)
         you will get -124. This is the documented method of how the INT works
         in QB, which in the case of the INT(-123.9), is NOT what we want,
         since we want -123.

   The following code takes the above conditions into consideration.
   * The absolute or ABS assures that the number to work with is positive.
   * This positive number is rounded by the rounding factor of "+.5".
   * The integer value INT is taken on the above positive result.
   * The sign of the original input number is restored by multiplying by the
     sign or SGN which is 1 for positive, -1 for negative, and 0 for zero.

   GIVEN:
   * N is the number to be rounded. Obviously, since it can have decimals,
     it must have a type declaration of single or double floating point.
     We will define it as single (!) for this example.
   * R will be the resultant rounded whole number.

   R = SGN(N!) * INT(ABS(N!) + .5)

*****


Title: Challenge: Algorithms having only one line of code.
Post by: Dr_Davenstein on March 20, 2006, 02:09:35 AM
Why couldn't you just do this?

Code:
Function Round( n As Single ) As Integer
    Round = n\1
End Function


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 20, 2006, 05:04:40 PM
Quote from: "Dr_Davenstein"
Why couldn't you just do this?

Code:
Function Round( n As Single ) As Integer
    Round = n\1
End Function


I've never tried your approach using integer division. The manual says that the variable is first "rounded" to an integer or long before the divide. That's great, but which of the 8 Microsoft defined rounding methods does it perform?

Give me a chance to test it on my DOS machine, and I'll get back to you.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 20, 2006, 05:20:36 PM
In my post of yesterday, I stated the following:
" .... I discovered that using a rounding factor of .5 or -.5 does not work 100% for reasons unknown."

Well, I wrote a little test program and discovered that the INT function in QB produces different results depending on the sign of the variable. An INT(-123.9) works differently than INT(123.9).

Since my original algorithm maintains the sign of the variable and uses a positive or negative rounding factor, then the INT with negative numbers does not always work like you would assume.

To appreciate this, you have to do some testing with the same positive and negative numbers with decimal values of .0, .4, .5, .6, and .9.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Ralph on March 20, 2006, 07:24:02 PM
In the spirit of the originally stated "to turn a switch on and off", would the very often used following line qualify?
Code:
IF A = 1 THEN A = 0 ELSE A = 1


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 21, 2006, 12:07:37 AM
Quote from: "Moneo"
Quote from: "Dr_Davenstein"
Why couldn't you just do this?

Code:
Function Round( n As Single ) As Integer
    Round = n\1
End Function


I've never tried your approach using integer division. The manual says that the variable is first "rounded" to an integer or long before the divide. That's great, but which of the 8 Microsoft defined rounding methods does it perform?

Give me a chance to test it on my DOS machine, and I'll get back to you.
*****


I did some testing. The n\1 yields mostly good rounding EXCEPT when the the number n is even and has a .5 decimal value. This rounding method is called Banker's Rounding. The one which we all use and which we are implementing here is Symmetric Arithmetic Rounding.

Example: 124.5 rounded should give 125. The n\1 approach gives 124.

Nice try!
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 21, 2006, 12:10:08 AM
Quote from: "Ralph"
In the spirit of the originally stated "to turn a switch on and off", would the very often used following line qualify?
Code:
IF A = 1 THEN A = 0 ELSE A = 1

Yeah, that works Ralph, but we have been considering as algorithms that code which does not have any IF's. That is, strictly computational, either arithmetic or logical.
*****


Title: Re: Challenge: Algorithms having only one line of code.
Post by: Ralph on March 21, 2006, 12:19:04 AM
Quote from: "Moneo"
Code:

Ok, here's the rules:

1) It must be considered an algorithm, formula or method.
    Add 15 to X   ----   X=X+15    This is not an algorithm, agreed?
    If it were, then every line of code in a program would be.

2) You must describe the algorithm first, i.e., what is its purpose.

3) Then show the one line of code.

4) Multiple statments on one line; like: x=x+1 : x=x and 15
    are not considered as one line of code.

A good example is one we've already seen with the XOR.
The purpose is to turn a switch on if it's off, and turn it off if it's on.
The one line of code is: sw=sw xor sw
or equally cool:              sw=1-sw

*****

Now, I quote once more, your second to last line, above, as:
Quote
The purpose is to turn a switch on if it's off, and turn it off if it's on.

Which is exactly what the one-liner I submitted does.  Or, have I mis-read your original rules?


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 22, 2006, 01:35:33 AM
Ok, Ralph, we'll allow your one liner with an IF THEN ELSE.

This issue came up in the past. I personally don't consider a statement with an IF to be an algorithm, but some people do.

So now, try to come up with some other algorithms using only one line of code.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Nemesis on March 27, 2006, 10:11:59 AM
'
coloums% = 6: rows% = 42:odds& = 1:FOR x = 1 TO coloums: odds& = odds& * ((rows + 1) - x) / x:NEXT:CLS : PRINT odds&

This is an algorithm for finding the odds of a lottery wheel.


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 27, 2006, 04:55:38 PM
Quote from: "Nemesis"
'
coloums% = 6: rows% = 42:odds& = 1:FOR x = 1 TO coloums: odds& = odds& * ((rows + 1) - x) / x:NEXT:CLS : PRINT odds&

This is an algorithm for finding the odds of a lottery wheel.


That looks like a cool algorithm, EXCEPT it is not on only one line of code, as per the original rules for this thread, which stated:

4) Multiple statements on one line; like:
x=x+1 : x=x and 15
are not considered as one line of code.

The idea of one line algorithms is that they're simple, most people can immediately understand them, they serve as an example for similar simple logic, and people can later use them in their programs when needed.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Ralph on March 28, 2006, 12:05:18 AM
Moneo:

Here's another one-liner to turn a switch on and off, in accordance with, and I quote you, "Most programmers consider TRUE as -1, and FALSE as 0."

x = -1 - x

Starting with x = 0, the next time it encounters the above, the new value will be, x = - 1, then, x = 0, then, x = -1, and so on...

In other words, as long as the previous value of x is 0 or -1, the one-liner will toggle the value of x to either -1 or 0, etc.


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on March 28, 2006, 11:02:38 AM
Quote from: "Moneo"
Quote from: "Ralph"
In the spirit of the originally stated "to turn a switch on and off", would the very often used following line qualify?
Code:
IF A = 1 THEN A = 0 ELSE A = 1

Yeah, that works Ralph, but we have been considering as algorithms that code which does not have any IF's. That is, strictly computational, either arithmetic or logical.
*****


Code:
A = 1 - A


Title: Challenge: Algorithms having only one line of code.
Post by: Dr_Davenstein on March 28, 2006, 07:30:32 PM
Did someone already post this one?

Code:
A = NOT A


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 28, 2006, 09:56:04 PM
Quote from: "na_th_an"
Quote from: "Moneo"
Quote from: "Ralph"
In the spirit of the originally stated "to turn a switch on and off", would the very often used following line qualify?
Code:
IF A = 1 THEN A = 0 ELSE A = 1

Yeah, that works Ralph, but we have been considering as algorithms that code which does not have any IF's. That is, strictly computational, either arithmetic or logical.
*****


Code:
A = 1 - A


Yeah, Nathan, that's very good. But we should always define that this algorithm will flip a switch which is either 0 or 1. BTW I forgot to mention this in the examples of the original rules of the thread.

NOTE: Speaking of those examples, the following code is incorrect for flipping a 0 or 1 switch called sw:
sw = sw xor sw
It should be:
sw = sw xor 1

I'm surprised nobody caught that.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 28, 2006, 10:41:23 PM
Quote from: "Ralph"
Moneo:

Here's another one-liner to turn a switch on and off, in accordance with, and I quote you, "Most programmers consider TRUE as -1, and FALSE as 0."

x = -1 - x

Very good Ralph, I never saw that before.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 28, 2006, 10:45:35 PM
Quote from: "Dr_Davenstein"
Did someone already post this one?

Code:
A = NOT A

Yes, LooseCaboose posted it back in the early days of the thread. But that's ok, it happens to be my favorite. Of course we're talking about flipping a switch that's 0 or -1.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: na_th_an on March 29, 2006, 09:01:58 AM
Quote from: "Moneo"
Quote from: "na_th_an"
Quote from: "Moneo"
Quote from: "Ralph"
In the spirit of the originally stated "to turn a switch on and off", would the very often used following line qualify?
Code:
IF A = 1 THEN A = 0 ELSE A = 1

Yeah, that works Ralph, but we have been considering as algorithms that code which does not have any IF's. That is, strictly computational, either arithmetic or logical.
*****


Code:
A = 1 - A


Yeah, Nathan, that's very good. But we should always define that this algorithm will flip a switch which is either 0 or 1. BTW I forgot to mention this in the examples of the original rules of the thread.

NOTE: Speaking of those examples, the following code is incorrect for flipping a 0 or 1 switch called sw:
sw = sw xor sw
It should be:
sw = sw xor 1

I'm surprised nobody caught that.
*****


Sure, that's what it does. Flip 0 to 1, 1 to 0... It was just an oneliner for the multiline IF version.


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on March 29, 2006, 01:57:21 PM
Heres one that CoderJeff posted over at freebasic.net in a discussion on working out the angle between two points.

Code:
angle = Atan2(v.x - u.x, -(v.y - u.y)) * (180 / PI)


It returns a value from -180 To 180, so needs a small adjustment if you want to use 0-360, but i thought this was a great one liner.

Code:

    If angle < 0 Then angle += 360


Title: Challenge: Algorithms having only one line of code.
Post by: Anonymous on March 29, 2006, 02:09:10 PM
i saw this on fb,.net also. but, shouldnt it be angle += 360, regardless? because the way you have it now, -120, say, and 60, will return the same value.

angle = ( ( Atan2(v.x - u.x, -(v.y - u.y)) * (180 / PI) + 360 ) mod 360 )

not tested ;p


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on March 29, 2006, 02:19:19 PM
if you use mod then it reverts to integer, so i prefer the other way to keep the double precision.  It only needs the +360 when it returns a value from -180 To 0 which is why i used the < 0 compare.   Your version is a true one liner though which is cool.


Title: Challenge: Algorithms having only one line of code.
Post by: Anonymous on March 29, 2006, 02:24:43 PM
yeah... well coderJeff showed us both up with this one:

Code:
angle = 180 - Atan2 ( v.x - u.x, v.y - u.y ) * 180 / PI


haha, that guys a ninja


edit upon testing, that didn't work! so i borrowed a bit from dr_d, that is, making radian transform a literal. here ya go:

Code:
angle =  180 - ATan2 ( v.x - u.x, v.y - u.y ) * 57.29577951308232


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on March 29, 2006, 02:46:22 PM
Quote
angle =  180 - ATan2 ( v.x - u.x, v.y - u.y ) * 57.29577951308232


this one gives me the wrong answer when angle = 0, it returns -6.24.....e015 or something


Title: Challenge: Algorithms having only one line of code.
Post by: Anonymous on March 29, 2006, 02:52:39 PM
correct you are. but i mean thats like

.0000000000000006


...so its pretty close to zero, hahahah. all other angles work.


Title: my one-liner
Post by: neuro on March 29, 2006, 04:08:42 PM
Here's my one-liner:

Draw a circle, without using the CIRCLE command:

Code:
SCREEN 12: h = 200: k = 200: r = 100: c = 13: FOR x = 0 TO INT(r / SQR(2)) + 1: y = SQR(r ^ 2 - x ^ 2): FOR a = -1 TO 1 STEP 2: FOR b = -1 TO 1 STEP 2: PSET (h + x * a, k + y * b), c: PSET (h + y * a, k + x * b), c: NEXT: NEXT: NEXT


draws a circle with center at (h, k), radius r and color c without using the CIRCLE command, or SIN or COS, and just two PSET commands.

It may seems like a long line but it fits inside a QBASIC IDE line of code. ;)

 - neuro


[edit]: I see one of the rules is, no compounded lines (with colons)...

Here's another of my favorite algorithms:

purpose: hang the computer uninterruptibly (written in C):

   for ( ; ; fork() ) ;

or this one, which goes on and on 4ever... (or just uses up all stack space):

int func(int x) return func(x+1);


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on March 29, 2006, 04:13:30 PM
Old thread, I don't know if i have posted this before:
Insert this in a line printing loop to print page by page
Code:

if lcnt=maxlines then print "Press a key";: x$=input$(1):lcnt=0:cls else lcnt=lcnt+1


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 29, 2006, 05:26:31 PM
Quote from: "Antoni Gual"
Old thread, I don't know if i have posted this before:
Insert this in a line printing loop to print page by page
Code:

if lcnt=maxlines then print "Press a key";: x$=input$(1):lcnt=0:cls else lcnt=lcnt+1

Nice bit of code, Antoni, but it's not one line of code by the established rules.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: relsoft on March 29, 2006, 11:24:58 PM
Code:
x = y * (((z AND 1) = 1) OR 1)


x = -y or + y depending on z being odd or even


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 30, 2006, 08:52:15 PM
Quote from: "relsoft"
Code:
x = y * (((z AND 1) = 1) OR 1)


x = -y or + y depending on z being odd or even

Ok, but what would I use this algorithm for?
*****


Title: Challenge: Algorithms having only one line of code.
Post by: relsoft on March 31, 2006, 03:09:34 AM
GFX effects. :*)

Mostly plasmas and sinewave displacement.


Title: Challenge: Algorithms having only one line of code.
Post by: Ralph on March 31, 2006, 05:20:49 PM
O.K., Moneo, you have had a few responses.  Now, what are you going to do with them?  I envision you will cull them, arrange them in some order, with a nice description preceding each one, and sort of customize there presentation, besides providing a neat identifiction tag for each one.  If that is your intention, it might be a good idea to let the folks know your intentions, publish what you have so far, and further invite more posts on the subject.

Regards,

Ralph


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on March 31, 2006, 11:06:58 PM
Quote from: "Ralph"
O.K., Moneo, you have had a few responses.  Now, what are you going to do with them?  I envision you will cull them, arrange them in some order, with a nice description preceding each one, and sort of customize there presentation, besides providing a neat identifiction tag for each one.  If that is your intention, it might be a good idea to let the folks know your intentions, publish what you have so far, and further invite more posts on the subject.

Regards,
Ralph

I revived this old thread for the purpose of correcting a rounding algorithm that I had posted back in 2003. I was concerned that someone might be using that old algorithm and sometimes getting wrong results while rounding negative numbers.

Then people started posting other algorithms, and the thread got started up again.

I already have a tutorial on algorithms which I wrote a few years ago for QBNZ. I might consider updating this tutorial for publication on the QB Express, in which case I'll scan this entire thread again to pick up any algorithms which in my opinion are worth including. This tutorial already gives credit to the author of each algorithm.

I agree with you had I intended to publish these algorithms. Yes, letting everyone know would have been a good idea. However, as I said before, this was not my intention. If you have the inclination to publish these algorithms, you're entirely free to do so.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on April 01, 2006, 11:28:43 AM
Heres the plan

1.  Ask for Algorithms.
2. ??????
3. Profit


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on April 26, 2006, 12:04:27 PM
Heres a couple i came across recently that i found quite interesting.  They are for testing if an addition or subtraction causes an overflow (ie the result is out of signed range)

These examples assume that a and b are 16-bit signed values.  This can be changed by changing the AND &H8000 to other values (ie &H80 for 8-bit).

Here is a link to a topic where redcrab explained to me exactly how they work

http://www.freebasic.net/forum/viewtopic.php?t=3914

Addition
Code:
overflow = ((a XOR (NOT b)) AND (a XOR (a + b)) AND &H8000) <> 0


Subtraction
Code:
overflow = ((a XOR b) AND (a XOR (a - b)) AND &H8000) <> 0


Title: Challenge: Algorithms having only one line of code.
Post by: Moneo on April 26, 2006, 09:49:29 PM
Vert good, Yetifoot, these algorithms for detecting overflow could come in handy for not having to use ON ERROR.
*****


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on April 27, 2006, 01:37:49 PM
I think they would have to be modified for use in QB, because the code itself will cause an overflow (due to a+b, or a-b).  They are more useful for FB, because FB does not do overflow checks (unless it's switched on with -ex, or -exx).


Title: Challenge: Algorithms having only one line of code.
Post by: Antoni Gual on May 03, 2006, 02:55:30 PM
QBasic does not signal overflow if compiled without the /d  option. Only interpreted QB always signals overflows, and your code would fail there.


Title: Challenge: Algorithms having only one line of code.
Post by: yetifoot on May 05, 2006, 09:01:07 AM
Quote from: "Antoni Gual"
QBasic does not signal overflow if compiled without the /d  option. Only interpreted QB always signals overflows, and your code would fail there.


Thanks for the clarification, I have not used QB/QBASIC much so I don't know much about it.