| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 842.1 | | PLDVS2::YOUNG | Back from the Shadows Again, | Sat Mar 12 1988 19:21 | 2 |
| What is "p" in your equation? Also some of the closure seems ambiguous
to me, could you clarify?
|
| 842.2 | | ELWD2::CHINNASWAMY | | Sun Mar 13 1988 18:22 | 22 |
|
> What is "p" in your equation? Also some of the closure seems ambiguous
> to me, could you clarify?
I thought I explained everything. Here is some more explanation:
N Min(n,M)
== ==
\ (N,n)*p^n*(1-p)^(N-n) \ (k-B)*k!*S(n,k)*(M,k)/M^n
/ /
== ==
n = B+1 k=B+1
where S(N,k) is the Stirling number of the second kind and (M,k) denotes
the combination of N things taken k at a time and p^n denotes p raised to
the power n , p is probability ( Assume any value, if a numerical value is
desired. But an algebraic expression is needed), k! denotes the factorial
of k, etc.
I have added a few asterisks to denote multiplication.
|
| 842.3 | Faster Program: | PLDVS2::YOUNG | Back from the Shadows Again, | Sun Mar 13 1988 23:06 | 161 |
| Well, if all you want or need is to get an answer faster, the following
program seems to complete in less than 1/10 th of a second on an
VAX 8250.
I cannot check it for correctness, as I do not know the correct
answers. If this has bugs or is not what you need let me know.
-- Barry
-----------------CROSS_BAR.FOR-------------------------------------------
OPTIONS /G_FLOAT
Program CROSS_BAR
Implicit none
Include 'COMMONDEF.FOR'
External Chins_problem
Real*8 Chins_problem, Temp, p
Integer N, M, B, I
!--
Type *, 'Enter p (probabilty): '
Accept *, p
Do while (1.eq.1)
Type *, 'Enter N,M,B : '
100 Format (I,I,I)
Accept 100, N, M, B
Type *, N, M, B
Temp = Chins_problem ( N, M, B, p )
Type *, temp
End do
End
!----
OPTIONS /G_FLOAT /extend_source
Real*8 function CHINS_PROBLEM ( N, M, B, p )
!++++
!
! This subroutine calculates the solution to the solution to the formula
! posted int MATH::842 by CHINNASWAMMY, which is:
!
! N Min(i,M)
! == ==
! \ (N,i)p^i(1-p)^(N-i) \ (k-B)*k!S2(i,k)(M,k)/M^i
! / /
! == ==
! i = B+1 k=B+1
!
! Where (M,k) is the number of combinations of M things taken k at a
! time, and S2(i,k) is a stirling number of the second kind.
!
!----
Implicit none
Include 'COMMONDEF.FOR'
Real*8 Fact, S2, Comb, Sum1, Sum2
Integer First_time /1/
Integer I, J, K, L
Integer M, N, B
Real*8 p
Fact(l) = Factl(l+1)
S2(l,j) = stirl(j,l)
Comb(l,j)= fact(l) / ( fact(j)*fact(l-j) )
!--
If ( first_time ) then
Call Init_factorials
Call Init_stirling2
First_time = 0
End if
Sum1 = 0
Do i = B+1, N
Sum2 = 0
Do k = B+1, Min(M,i)
Sum2 = Sum2 + (k-B) * Fact(k) * S2(i,k) * Comb(M,k)
End do
Sum1 = Sum1 + ( Comb(N,i) * p**i * ((1-p)**(N-i)) * Sum2 )
+ / ( Dble(M)**i )
End do
Chins_problem = Sum1
End
!----
OPTIONS /G_FLOAT
Subroutine INIT_FACTORIALS
Implicit none
Include 'COMMONDEF.FOR'
Integer I
!--
Factl ( 1 ) = 1
Do i = 2, 101
Factl (i) = Factl (i-1) * i-1 ! Offset 1 to account
! for (0!).
End do
End
!----
OPTIONS /G_FLOAT
Subroutine INIT_STIRLING2
Implicit none
Include 'COMMONDEF.FOR'
Integer I, J
!--
Do i = 1, 100
Stirl ( 1, i ) = 1
Stirl ( i, i ) = 1
Do j = 2, i-1
Stirl ( j, i ) = j * stirl(j,i-1) + stirl(j-1,i-1)
End do
End do
End
-------------------------COMMONDEF.FOR-------------------------------------
Real*8 Factl(101), Stirl(100,100)
Common /Funct_vals/
+ Factl,
+ Stirl
|
| 842.4 | Typo in Factorial routine | SSDEVO::LARY | | Mon Mar 14 1988 09:43 | 4 |
| Factl(i) = factl(i-1) * i-1
should be: Factl(i) = factl(i-1) * (i-1)
|
| 842.5 | Gaaaahhhhh!!!! | PLDVS2::YOUNG | Back from the Shadows Again, | Mon Mar 14 1988 10:12 | 158 |
| Thanks for the sanity-check.
Corrected version follows:
-----------------CROSS_BAR.FOR-------------------------------------------
OPTIONS /G_FLOAT
Program CROSS_BAR
Implicit none
Include 'COMMONDEF.FOR'
External Chins_problem
Real*8 Chins_problem, Temp, p
Integer N, M, B, I
!--
Type *, 'Enter p (probabilty): '
Accept *, p
Do while (1.eq.1)
Type *, 'Enter N,M,B : '
100 Format (I,I,I)
Accept 100, N, M, B
Type *, N, M, B
Temp = Chins_problem ( N, M, B, p )
Type *, temp
End do
End
!----
OPTIONS /G_FLOAT /extend_source
Real*8 function CHINS_PROBLEM ( N, M, B, p )
!++++
!
! This subroutine calculates the solution to the solution to the formula
! posted int MATH::842 by CHINNASWAMMY, which is:
!
! N Min(i,M)
! == ==
! \ (N,i)p^i(1-p)^(N-i) \ (k-B)*k!S2(i,k)(M,k)/M^i
! / /
! == ==
! i = B+1 k=B+1
!
! Where (M,k) is the number of combinations of M things taken k at a
! time, and S2(i,k) is a stirling number of the second kind.
!
!----
Implicit none
Include 'COMMONDEF.FOR'
Real*8 Fact, S2, Comb, Sum1, Sum2
Integer First_time /1/
Integer I, J, K, L
Integer M, N, B
Real*8 p
Fact(l) = Factl(l+1)
S2(l,j) = stirl(j,l)
Comb(l,j)= fact(l) / ( fact(j)*fact(l-j) )
!--
If ( first_time ) then
Call Init_factorials
Call Init_stirling2
First_time = 0
End if
Sum1 = 0
Do i = B+1, N
Sum2 = 0
Do k = B+1, Min(M,i)
Sum2 = Sum2 + (k-B) * Fact(k) * S2(i,k) * Comb(M,k)
End do
Sum1 = Sum1 + ( Comb(N,i) * p**i * ((1-p)**(N-i)) * Sum2 )
+ / ( Dble(M)**i )
End do
Chins_problem = Sum1
End
!----
OPTIONS /G_FLOAT
Subroutine INIT_FACTORIALS
Implicit none
Include 'COMMONDEF.FOR'
Integer I
!--
Factl ( 1 ) = 1
Do i = 2, 101
Factl (i) = Factl (i-1) * (i-1) ! Offset 1 to account
! for (0!).
End do
End
!----
OPTIONS /G_FLOAT
Subroutine INIT_STIRLING2
Implicit none
Include 'COMMONDEF.FOR'
Integer I, J
!--
Do i = 1, 100
Stirl ( 1, i ) = 1
Stirl ( i, i ) = 1
Do j = 2, i-1
Stirl ( j, i ) = j * stirl(j,i-1) + stirl(j-1,i-1)
End do
End do
End
-------------------------COMMONDEF.FOR-------------------------------------
Real*8 Factl(101), Stirl(100,100)
Common /Funct_vals/
+ Factl,
+ Stirl
|
| 842.6 | it's not "times (i-1)" | ZFC::DERAMO | performing without a net | Mon Mar 14 1988 19:50 | 13 |
| Re .4:
>> -< Typo in Factorial routine >-
>>
>> Factl(i) = factl(i-1) * i-1
>>
>> should be: Factl(i) = factl(i-1) * (i-1)
factorial(i) = 1 * 2 * ... * (i - 1) * i
= factorial(i - 1) * i
Dan
|
| 842.7 | Some hand-waving here... | CHOVAX::YOUNG | Back from the Shadows Again, | Tue Mar 15 1988 00:27 | 13 |
| Actually Dan, I think that this is explained in the comments which
are in the program.
Since FORTRAN has 1's based arrays, the array Factl() could not
return the value of 0! if the mapping of array index and function
argument were exact. Therefore I bulit in a 1 place shift so that
Factl(1) = 0!, and in general Factl(i) = (i-1)! . For clarity I
define a FORTRAN statement function elsewhere called Fact() that
makes the 1 step translation so that Fact(i) = Factl(i+1) = i!
So this should be correct.
-- Barry
|
| 842.8 | | ELWD2::CHINNASWAMY | | Tue Mar 15 1988 07:38 | 16 |
|
Barry,
Thanks for your solution. The only difference, if I recall correctly
between my program and yours is that I wrote it in Pascal, there was
one more term in the calculation, I calculated for several values of
p and submitted it as a batch job. But these things should not make
that much of a difference in compute time. I will look at the
difference more carefully this weekend.
It would be nice if we can find an algebraic expression.
Again, thanks for your help.
Swamy
|
| 842.9 | | ZFC::DERAMO | performing without a net | Tue Mar 15 1988 11:25 | 7 |
| Re .7, factorials etc.
I suspected that it might have been "out of context", but I
had skipped over the program. I was going to suggest that you
rename the function to Gamma. (-:
Dan
|
| 842.10 | | PLDVS1::YOUNG | Back from the Shadows Again, | Tue Mar 15 1988 12:05 | 7 |
| Re .8:
Did your Pascal program also precalculate the Factorial and Strirling
values? This change in my program made it an order O(n^2) program
instead of the order O(n^4) program that it was originally.
-- Barry
|
| 842.11 | Hey, what the heck is a Cross-bar switch? | CHOVAX::YOUNG | Back from the Shadows Again, | Sat Mar 19 1988 07:07 | 1 |
|
|
| 842.12 | Stirling numbers and cross bar | ELWD2::CHINNASWAMY | | Sun Mar 27 1988 20:14 | 17 |
| The following three references will give an idea of what a cross bar
switch is and where the formulas came from:
1. Yu-cheng Liu and Chi-jiunn Jou, "Effective Memory Bandwidth and
Processor Blocking Probability in Multiple-Bus Systems", IEEE Trans.
Comput., Vol. C-36, No. 6, pp 761 - 764, June 1987
2. D. Y. Chang, D. J. Kuck,, and D. H. Lawrie, "On the Effective Bandwidth
of Parallel Memories", IEEE Trans. Comput., vol. c-26, pp. 480-490, May
1977.
3. T. Lang, M. Valero, and I. Alegre, "Bandwidth of crossbar and multiple-
bus connections for multiprocessors", IEEE Trans. Comput., vol. C-31,
pp. 1227-1234, CDec. 1982.
swamy
|