What Are The Odds ?

[MrBcx]

I thought that your statement meant that UBOUND() is only 95% correct

That is certainly not the case. 

UBOUND() is always 100% correct except when it is 0% correct.   

[jbk]

I thought that your statement meant that UBOUND() is only 95% correct

[MrBcx]

... only using UBOUND() should only produce correct results 95% of the time.

please explain

https://bcxbasiccoders.com/smf/index.php?topic=1362.msg7444#msg7444

Probably just more flawed thinking ...

[jbk]

... only using UBOUND() should only produce correct results 95% of the time.

please explain

[MrBcx]

the result from the BCXHELP example was always correct

MrBcx:

The result from the BCXHELP example is wrong if the smallest number is in the twentieth position.

Here are the results I got when I ran the BCXHELP code. The results are wrong.

Code Select Expand

74.9573447879171
 51.1835801684868
 38.9997049900451
 73.8114214264548
 81.2150802274883
 51.0521236789161
 81.1140371218264
 14.4046135543761
 78.5340048254377
 72.4890035314828
 33.7353237313405
 43.5777465218264
 32.8451694241807
 54.0559815774512
 81.882011996485
 86.0418916580951
 26.3334760245693
 93.8873747337806
 67.8885582023263
 11.3100325375497

Smallest Value: 14.4046135543761

Press any key to continue . . .

This wrong result, from the randomly generated input in the BCXHELP function, is what caused me to make my original post in this thread wondering what would be the odds of the smallest number being positioned at the bottom of the list.

Your "correction" of the "flawed" (sic) code is a "disgusting abomination" when compared to your elegant original adaptation of kmkaplan's code.
 

Yup ... I get it now.  kaplan's code and the BCXHELP version of it require the
actual number of cells not the value returned by UBOUND(). Relative to the
examples, only using UBOUND() should only produce correct results 95% of the time.

[Robert]

the result from the BCXHELP example was always correct

MrBcx:

The result from the BCXHELP example is wrong if the smallest number is in the twentieth position.

Here are the results I got when I ran the BCXHELP code. The results are wrong.

Code Select Expand

74.9573447879171
 51.1835801684868
 38.9997049900451
 73.8114214264548
 81.2150802274883
 51.0521236789161
 81.1140371218264
 14.4046135543761
 78.5340048254377
 72.4890035314828
 33.7353237313405
 43.5777465218264
 32.8451694241807
 54.0559815774512
 81.882011996485
 86.0418916580951
 26.3334760245693
 93.8873747337806
 67.8885582023263
 11.3100325375497

Smallest Value: 14.4046135543761

Press any key to continue . . .

This wrong result, from the randomly generated input in the BCXHELP function, is what caused me to make my original post in this thread wondering what would be the odds of the smallest number being positioned at the bottom of the list.

Your "correction" of the "flawed" (sic) code is a "disgusting abomination" when compared to your elegant original adaptation of kmkaplan's code.

[MrBcx]

Hi Robert,

What didn't make sense was that the BCXHELP example and your example
both had 20 pieces of data in their arrays.  And when using the function
in the BCXHELP, the result from the BCXHELP example was always correct
but your example was always wrong.

The updated function produces the correct results for both examples by
simply specifying UBOUND() without including +1 in your example.

Here is what Claude had to say about the problem:

When the smallest value is at index 19, and you call FindSmallest(BUF, 19), the
recursion stops when cellnumber reaches 1, but at that point it never actually
compares against the element at index 19 - it stops before reaching it.

 

[Robert]

Robert,

It turns out that FUNCTION FindSmallest() is flawed.

It doesn't properly handle the edge case where the minimum element is at the highest index position.

Here is a revised function that works correctly using both your sample and the sample from BCXHELP.

Code Select Expand


FUNCTION FindSmallest(column[] AS DOUBLE, highestIndex AS INT) AS DOUBLE
    DIM firstElement AS DOUBLE
    DIM lastElement  AS DOUBLE

    IF highestIndex = 0 THEN
        FUNCTION = column[0]
    END IF

    firstElement = column[0]
    lastElement  = column[highestIndex]

    IF firstElement <= lastElement THEN
        FUNCTION = FindSmallest(column, highestIndex - 1)
    ELSE
        FUNCTION = FindSmallest(column + 1, highestIndex - 1)
    END IF
END FUNCTION



MrBcx:

I don't think that the original code from
  '***********************************************************************************************************
  ' Original function by (kmkaplan)
  ' https://stackoverflow.com/questions/13596455/finding-the-minimum-element-of-an-array-using-tail-recursion
  '***********************************************************************************************************
nor the function in the Help file example are flawed.

They both expect to be passed the number of elements in the array, not the UBOUND of the array.

Below is an example using the original kmkaplan C code function modified to take DOUBLE instead of INTEGER values.

Code Select Expand

SET BUF[] AS DOUBLE
74.9573447879171,
51.1835801684868,
38.9997049900451,
73.8114214264548,
81.2150802274883,
51.0521236789161,
81.1140371218264,
14.4046135543761,
78.5340048254377,
72.4890035314828,
33.7353237313405,
43.5777465218264,
32.8451694241807,
54.0559815774512,
81.8820119964850,
86.0418916580951,
26.3334760245693,
93.8873747337806,
67.8885582023263,
11.3100325375497
END SET

FOR INT i = 0 TO UBOUND(BUF)
  PRINT BUF#[i]                ' Show them to us
NEXT

PRINT
PRINT "Smallest Value:", f#(BUF, UBOUND(BUF) + 1)  ' Find smallest value in our unsorted array

$CCODE FUNCSUB

double f(double a[], int n)
{
    if (n == 1)
        return a[o];
    n--;
    return f(a + (a[o]> a[n]), n);
}

$CCODE


Result:
Smallest Value: 11.3100325375497

[MrBcx]

Robert,

It turns out that FUNCTION FindSmallest() is flawed.

It doesn't properly handle the edge case where the minimum element is at the highest index position.

Here is a revised function that works correctly using both your sample and the sample from BCXHELP.

Code Select Expand


FUNCTION FindSmallest(column[] AS DOUBLE, highestIndex AS INT) AS DOUBLE
    DIM firstElement AS DOUBLE
    DIM lastElement  AS DOUBLE

    IF highestIndex = 0 THEN
        FUNCTION = column[0]
    END IF

    firstElement = column[0]
    lastElement  = column[highestIndex]

    IF firstElement <= lastElement THEN
        FUNCTION = FindSmallest(column, highestIndex - 1)
    ELSE
        FUNCTION = FindSmallest(column + 1, highestIndex - 1)
    END IF
END FUNCTION



[Robert]

The recursive FindSmallest function will correctly identify whichever number happens to be smallest

Claude is correct.

Unfortunately, however, the smallest number in the Result: list is the last number, 11.3100325375497; while the program reports Smallest Value: 14.4046135543761.

The off-by-one error is due to to the FindSmallest function call

Code Select Expand

PRINT "Smallest Value:", FindSmallest#(BUF, UBOUND(BUF))  ' Find smallest value in our unsorted array
which does not process the last number in the list.

The corrected FindSmallest function call is

Code Select Expand

PRINT "Smallest Value:", FindSmallest#(BUF, UBOUND(BUF) + 1)  ' Find smallest value in our unsorted array
Below is test code

Code Select Expand

SET BUF[] AS DOUBLE
 74.9573447879171,
 51.1835801684868,
 38.9997049900451,
 73.8114214264548,
 81.2150802274883,
 51.0521236789161,
 81.1140371218264,
 14.4046135543761,
 78.5340048254377,
 72.4890035314828,
 33.7353237313405,
 43.5777465218264,
 32.8451694241807,
 54.0559815774512,
 81.8820119964850,
 86.0418916580951,
 26.3334760245693,
 93.8873747337806,
 67.8885582023263,
 11.3100325375497
END SET

FOR INT i = 0 TO UBOUND(BUF)
  PRINT BUF#[i]                ' Show them to us
NEXT

PRINT
PRINT "Off by 1."
PRINT "Smallest Value:", FindSmallest#(BUF, UBOUND(BUF))  ' Find smallest value in our unsorted array
PRINT "Right on !"
PRINT "Smallest Value:", FindSmallest#(BUF, UBOUND(BUF) + 1)  ' Find smallest value in our unsorted array

PAUSE

FUNCTION FindSmallest (column[] AS DOUBLE, cellnumber AS INT) AS DOUBLE
  '***********************************************************************************************************
  ' Original function by (kmkaplan)
  ' https://stackoverflow.com/questions/13596455/finding-the-minimum-element-of-an-array-using-tail-recursion
  '***********************************************************************************************************
  IF cellnumber = 1 THEN
    FUNCTION = column[0]
  ELSE
    DECR cellnumber
    FUNCTION = FindSmallest(column + (column[0] > column[cellnumber]), cellnumber)
  END IF
END FUNCTION


[MrBcx]

Here is what Claude said ...

The code creates an array of 21 random numbers (indices 0-20, since UBOUND(BUF) returns 20), where each number is generated
using RND * 99.13579. The RND function typically produces uniform random numbers between 0 and 1, so each array element will
be a uniform random number between 0 and 99.13579.

For the probability calculation:
The odds that the last number (at index 20) is the smallest among all 21 numbers is exactly 1/21.
Here's why:

Symmetry of uniform random variables: Since all 21 numbers are generated independently from the same uniform distribution,
each number has an equal probability of being the minimum.
Equal likelihood principle: By symmetry, each of the 21 positions has exactly the same chance of containing the smallest value.

Mathematical proof:
For any set of n independent, identically distributed continuous random variables, the probability that any specific one is the minimum is 1/n.

Therefore, the probability is:

1/21 ≈ 0.0476 or about 4.76%

This would be true regardless of:

The specific scaling factor (99.13579)
The random number generator used (as long as it produces continuous uniform distributions)
Which position we're asking about (first, last, or any specific position)

The recursive FindSmallest function will correctly identify whichever number happens to be smallest, but due to the random nature
of the generation, each position has an equal 1/21 chance of containing that minimum value.

[Robert]

What are the odds that the last number in the result list of random numbers produced by

Example 2: from 'Recursive FUNCTION and SUB procedures' section of BCX Help

would be the smallest number ?

Code Select Expand

RANDOMIZE TIMER

DIM BUF[20] AS DOUBLE

FOR INT i = 0 TO UBOUND(BUF)
  BUF[i] = RND * 99.13579      ' Fill our array with random values
  PRINT BUF#[i]                ' Show them to us
NEXT

PRINT
PRINT "Smallest Value:", FindSmallest#(BUF, UBOUND(BUF))  ' Find smallest value in our unsorted array

PAUSE


FUNCTION FindSmallest (column[] AS DOUBLE, cellnumber AS INT) AS DOUBLE
  '***********************************************************************************************************
  ' Original function by (kmkaplan)
  ' https://stackoverflow.com/questions/13596455/finding-the-minimum-element-of-an-array-using-tail-recursion
  '***********************************************************************************************************
  IF cellnumber = 1 THEN
    FUNCTION = column[0]
  ELSE
    DECR cellnumber
    FUNCTION = FindSmallest(column + (column[0] > column[cellnumber]), cellnumber)
  END IF
END FUNCTION

Result:

Code Select Expand


 74.9573447879171
 51.1835801684868
 38.9997049900451
 73.8114214264548
 81.2150802274883
 51.0521236789161
 81.1140371218264
 14.4046135543761
 78.5340048254377
 72.4890035314828
 33.7353237313405
 43.5777465218264
 32.8451694241807
 54.0559815774512
 81.882011996485
 86.0418916580951
 26.3334760245693
 93.8873747337806
 67.8885582023263
 11.3100325375497

Smallest Value: 14.4046135543761

Press any key to continue . . .